Full Abstraction for Signal Flow Graphs

September 11, 2017

Filippo Bonchi


Full Abstraction for Signal Flow Graphs

Time:   10:45am
Location:   Meeting room 302 (Mountain View), level 3

Signal Flow Graphs (SFGs) were introduced in the 1940s by Shannon as a formal circuit model of a class of simple analog computing machines. They are a common abstraction in control theory, signal processing and engineering, used for modelling physical systems and their controllers. Nowadays, cyber-physical systems are modelled, simulated and analysed in graphical environments such as Simulink and Modelica that can be seen as great-grandchildren of SFGs.

In this talk, we introduce a graphical syntax for signal flow graphs based on the language of string diagrams. Using universal constructions, we provide a denotational semantics and a sound and complete axiomatisation. The terms can be executed using a structural operational semantics. The problem of full abstraction raises novel and unexpected semantics issues.