Weighted Automata and Logics on Graphs

被引:7
作者
Droste, Manfred [1 ]
Dueck, Stefan [1 ]
机构
[1] Univ Leipzig, Inst Comp Sci, D-04109 Leipzig, Germany
来源
MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I | 2015年 / 9234卷
关键词
Quantitative automata; Graphs; Quantitative logic; Weighted automata; Buchi; Nivat; LANGUAGES;
D O I
10.1007/978-3-662-48057-1_15
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 Buchi-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.
引用
收藏
页码:192 / 204
页数:13
相关论文
共 35 条
[1]   Adding Nesting Structure to Words [J].
Alur, Rajeev ;
Madhusudan, P. .
JOURNAL OF THE ACM, 2009, 56 (03)
[2]  
[Anonymous], 1961, Transactions of the American Mathematical Society, DOI [DOI 10.1090/S0002-9947-1961-0139530-9, 10.1090/S0002-9947-1961-0139530-9]
[3]  
[Anonymous], 1960, Z. Math. Logik Grundlagen Math.
[4]  
[Anonymous], 1978, AUTOMATA THEORETIC A
[5]   Unambiguous recognizable two-dimensional languages [J].
Anselmo, Marcella ;
Giammarresi, Dora ;
Madonia, Maria ;
Restivo, Antonio .
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2006, 40 (02) :277-293
[6]  
Berstel J., 1988, EATCS MONOGRAPHS THE, V12
[7]   Pebble Weighted Automata and Weighted Logics [J].
Bollig, Benedikt ;
Gastin, Paul ;
Monmege, Benjamin ;
Zeitoun, Marc .
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2014, 15 (02)
[8]  
Bollig B, 2009, LECT NOTES COMPUT SC, V5583, P18
[9]  
Doner John, 1970, Journal of Computer and System Sciences, V4, P406, DOI DOI 10.1016/S0022-0000(70)80041-1
[10]  
Droste M, 2009, EATCS MONOGRAPHS