Weighted Automata and Logics on Graphs
Weighted Automata and Logics on Graphs
复制标题
加权自动机和图逻辑
DOI：
10.1007/978-3-662-48057-1_15
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
S. Dück
中科院分区：
文献类型：
--
作者：
M. Droste;S. Dück
加权自动机对系统行为的定量特征进行建模，并研究了各种结构，如词、树、痕迹、图片和嵌套词。本文引入了作用于图的加权自动机的一般模型，形成了Thomas图受体的非加权模型的定量化版本。我们导出了加权图自动机的Nivat定理，该定理证明了加权图自动机的行为与特定的加权图自动机和非加权图接受器的行为完全相同。我们还证明了一个合适的加权MSO逻辑在表达上等同于加权图自动机。因此，我们从最近的文献中获得了关于词、树、图片和嵌套词的加权自动机和加权逻辑的相应的b<s:1> chi型等价结果。一段时间以来，建立这样一个一般结果一直是加权逻辑的一个开放性问题。
Weighted automata model quantitative features of the behavior of systems and have been investigated for various structures like words, trees, traces, pictures, and nested words. In this paper, we introduce a general model of weighted automata acting on graphs, which form a quantitative version of Thomas’ unweighted model of graph acceptors. We derive a Nivat theorem for weighted graph automata which shows that their behaviors are precisely those obtainable from very particular weighted graph automata and unweighted graph acceptors with a few simple operations. We also show that a suitable weighted MSO logic is expressively equivalent to weighted graph automata. As a consequence, we obtain corresponding Büchi-type equivalence results known from the recent literature for weighted automata and weighted logics on words, trees, pictures, and nested words. Establishing such a general result has been an open problem for weighted logic for some time.
登录
查看更多内容
迹线的加权逻辑
DOI：
--
发表时间：
2006
期刊：
Computer Science Symposium in Russia
影响因子：
--
作者：
I. Meinecke
通讯作者：
I. Meinecke
DOI：
10.1007/978-3-642-73235-5
发表时间：
1988-11
期刊：
--
影响因子：
--
作者：
J. Berstel;C. Reutenauer
通讯作者：
J. Berstel;C. Reutenauer
加权树自动机和加权逻辑
影响因子：
1.1
作者：
M. Droste;H. Vogler
通讯作者：
H. Vogler
文本的可定义转换和加权逻辑
影响因子：
1.1
作者：
Christian Mathissen
通讯作者：
Christian Mathissen
无限嵌套词的加权自动机和逻辑
影响因子：
1
作者：
M. Droste;Stefan Dück
通讯作者：
Stefan Dück