Diagrammatic methods for linear and nonlinear systems
NII Shonan Meeting:
@ Shonan Village Center, November 26-29, 2018
- Dan R. Ghica, University of Birmingham, UK
- Masahito Hasegawa , Kyoto University, Japan
- Pawel Sobocinski, University of Southampton, UK
Description of the meeting
Circuit diagrams, signal flow graphs and related graphical formalisms are at the lingua franca of electric and electronic engineering, and systems theory. Recent work has focussed on the applications of string diagrams as a formal approach to these circuitlike notations. Diagrammatic reasoning is the driving methodology: formulas are replaced with diagrams, and calculation is performed by transforming diagrams according to a rigorous set of rules, which preserve the intended behaviour (semantics) of systems. Apart from intuitive aspects, the diagrammatic approach brings compositionality, an important principle in systems design. This workshop will bring together engineers, control and systems theorists, mathematicians and theoretical computer scientists, feature presentations about the diagrammatic approach, and focus on how it can be used to help solve current challenges in EEE and systems theory.
In theoretical physics, the graphical representation of subatomic particle interaction invented by Stückelberg and popularised by Feynman in the 1940s and 1950s represents a visually intuitive alternative to complex mathematical representations. Later on, in the 1980s, these diagrams were used to establish a bridge between quantum physics and topology. Subsequently, via a CurryHowardLambek
correspondence, broader connections with (linear) logic, computation and (monoidal) categories have been discovered. That similar mathematical structures can be encountered in such different contexts is not only fascinating in its own right but also potentially leading to new applications and methods of reasoning. The axiomatic (categorical) formalisation appears to be much more robust and simple than the concrete mathematical models. Moreover, the link to graph theory via diagrammatic representations opens the door to novel,
unforeseen, avenues of automating reasoning via graph rewriting. Very recent applications to quantum computing, systems theory and circuit design indicate significant early promise of this methodology.
Applications to quantum computing and protocols
The crossover into Computer Science took on a new impetus with Abramsky and Coecke’s seminal paper A Categorical Se mantics of Quantum Protocols, which initiated a remarkably productive programme of research which reformulated important aspects of quantum computing, quantum protocols and quantum mechanics in a diagrammatic framework. The theoretical results were complemented by the development of a new kind of proof assistant, a diagrammatic proof assistant1 which allows users to prove mathematical theorems automatically via graph rewrite rules.
Applications to systems theory and circuit design
The idea of a diagrammatic language for dynamical systems goes back to Shannon in the 1940s, who wrote about “linear differential equation machines”. In the 1950s Mason rediscovered this class of diagrams and called them signal flow graphs. Signal flow graphs describe systems with dynamics given by sets of linear constantcoefficient differential equations; in subsequent decades these led to advances via algebraic techniques by Rosenbrock in the 1970s and have led to a large body of influential work by JC Willems in the 1980s and 1990s. A series of recent papers by Baez, Bonchi, Erbele, Fong, Rapisarda and Sobocinski developed a category theoretic approach to signal flow graphs, leading to a behavioural theory of “tearing, zooming and linking” à la Willems. From the systems theoretic point of view, these results are promising since the compositional, diagrammatic techniques we bring to the subject seem wellsuited to problems such
as controllability of interconnections, of primary interest for multiagent and spatially interconnected systems.
In the case of circuits, diagrams are a common representational vernacular yet no diagramlevel reasoning techniques were, until recently, systematically developed. Categoricalstyle term languages for diagrams were pioneered by Sheeran in the 1980s, leading to embedded DSLs for circuit design, but an axiomatic treatment making a definitive connection to controlflow categories was only recently proposed by Ghica and Jung. This allows diagrammatic reasoning about circuits, which can be fully mechanised via graph rewriting, leading to a more syntactic counterpart to the interpretationbased reasoning methods which are established in circuit design. The diagrammatic approach promises to be simpler and more robust than the alternative, allowing reasoning about nonstandard circuits such as combinational circuits with feedback and powerful optimisation techniques such as partial evaluation or supercompilation.
Aims of the workshop
This interdisciplinary workshop will help bridge the gap between those active in the development of mathematical (and software) tools for diagrammatic reasoning and areas who stand to benefit from such methods, in particular systems theory and digital circuits specification,
design, optimisation, and verification. The benefits of this interaction will run both ways. Circuit designers and system theorists will
benefit from the development of these new methods of representation and reasoning and, in turn, will help the theorists focus on the real and difficult practical problems that they are confronted with. Moreover, closer interaction between these groups of researchers will highlight new, unforeseen, directions of development for and applications of the diagrammatic approach since underlying diagrammatic representation lie at the heart of many popular system design and specification methodologies (e.g. statecharts, SimuLink and alternatives).