Weighted Automata and Logics on Infinite Graphs

被引：0
|
作者：
Dueck, Stefan [1 ]
机构：
[1] Univ Leipzig, Inst Comp Sci, D-04109 Leipzig, Germany
来源：
DEVELOPMENTS IN LANGUAGE THEORY, DLT 2016 | 2016年 / 9840卷
关键词：
Quantitative automata; Infinite graphs; Graphs; Quantitative logic; Valuation monoids; TREE AUTOMATA;
D O I：
10.1007/978-3-662-53132-7_13
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We show a Buchi-like connection between graph automata and logics for infinite graphs. Using valuation monoids, a very general weight structure able to model computations like average or discounting, we extend this result to the quantitative setting. This gives us the first general results connecting automata and logics over infinite graphs in the qualitative and the quantitative setting.
引用
收藏
页码：151 / 163
页数：13
相关论文
共 50 条
  • [1] Weighted Automata and Logics on Graphs
    Droste, Manfred
    Dueck, Stefan
    MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2015, PT I, 2015, 9234 : 192 - 204
  • [2] Weighted automata and weighted logics on infinite words
    Droste, Manfred
    Rahonis, George
    DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, 2006, 4036 : 49 - 58
  • [3] Weighted Automata and Weighted Logics on Infinite Words
    Droste, M.
    Rahonis, G.
    RUSSIAN MATHEMATICS, 2010, 54 (01) : 26 - 45
  • [4] Weighted Automata and Logics for Infinite Nested Words
    Droste, Manfred
    Dueck, Stefan
    LANGUAGE AND AUTOMATA THEORY AND APPLICATIONS (LATA 2014), 2014, 8370 : 323 - 334
  • [5] Weighted automata and logics for infinite nested words
    Droste, Manfred
    Dueck, Stefan
    INFORMATION AND COMPUTATION, 2017, 253 : 448 - 466
  • [6] Weighted automata and weighted logics
    Droste, Manfred
    Gastin, Paul
    THEORETICAL COMPUTER SCIENCE, 2007, 380 (1-2) : 69 - 86
  • [7] Weighted automata and weighted logics
    Droste, M
    Gastin, P
    AUTOMATA, LANGUAGES AND PROGRAMMING, PROCEEDINGS, 2005, 3580 : 513 - 525
  • [8] Applications in Enumerative Combinatorics of Infinite Weighted Automata and Graphs
    De Castro, Rodrigo
    Ramirez, Andres
    Ramirez, Jose L.
    SCIENTIFIC ANNALS OF COMPUTER SCIENCE, 2014, 24 (01) : 137 - 171
  • [9] Weighted automata and weighted logics with discounting
    Droste, Manfred
    Rahonis, George
    IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2007, 4783 : 73 - +
  • [10] Weighted automata and weighted logics with discounting
    Droste, Manfred
    Rahonis, George
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (37) : 3481 - 3494
12345