Full Abstraction for Signal Flow Graphs
Full Abstraction for Signal Flow Graphs
复制标题
DOI：
10.1145/2775051.2676993
复制
发表时间：
2015-01-01
影响因子：
--
通讯作者：
Zanasi, Fabio
中科院分区：
文献类型：
--
作者：
Bonchi, Filippo;Sobocinski, Pawel;Zanasi, Fabio
网络理论使用Monoidal范畴的字符串图形语言来正式研究图形结构，避免将专门的翻译成中间形式主义。最近，已经有一个协调一致的研究重点是开发一个网络理论的方法，信号流图，这是经典的结构，在控制理论，信号处理和反馈的研究的基石。在这种方法中，信号流图被赋予了一种形式幂级数的关系指称语义，到目前为止，这种信号流图的操作行为只在直观的水平上进行了讨论。在本文中，我们配备了一个结构化的操作语义。通常情况下，纯粹的操作画面太具体了-两个在外延上相等的图可能会表现出不同的操作行为。我们分类的方式，这可能会发生，并表明，任何图形可以实现-重写，使用图形理论，到一个可执行的形式，其中的操作行为和外延相吻合。
Network theory uses the string diagrammatic language of monoidal categories to study graphical structures formally, eschewing specialised translations into intermediate formalisms. Recently, there has been a concerted research focus on developing a network theoretic approach to signal flow graphs, which are classical structures in control theory, signal processing and a cornerstone in the study of feedback. In this approach, signal flow graphs are given a relational denotational semantics in terms of formal power series.Thus far, the operational behaviour of such signal flow graphs has only been discussed at an intuitive level. In this paper we equip them with a structural operational semantics. As is typically the case, the purely operational picture is too concrete - two graphs that are denotationally equal may exhibit different operational behaviour. We classify the ways in which this can occur and show that any graph can be realised - rewritten, using the graphical theory, into an executable form where the operational behavior and the denotation coincides.