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 条
  • [21] The Rigidity of Infinite Graphs II
    D. Kitson
    S. C. Power
    Graphs and Combinatorics, 2022, 38
  • [22] Infinite Random Geometric Graphs
    Bonato, Anthony
    Janssen, Jeannette
    ANNALS OF COMBINATORICS, 2011, 15 (04) : 597 - 617
  • [23] Compactification of Infinite Graphs and Sampling
    Palle E. T. Jorgensen
    Myung-Sin Song
    Sampling Theory in Signal and Image Processing, 2013, 12 (2-3): : 139 - 158
  • [24] Pursuit evasion on infinite graphs
    Lehner, Florian
    THEORETICAL COMPUTER SCIENCE, 2016, 655 : 30 - 40
  • [25] Constructing infinite models represented by tree automata
    Peltier, Nicolas
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2009, 56 (01) : 65 - 85
  • [26] Tree Automata with Global Constraints for Infinite Trees
    Landwehr, Patrick
    Loeding, Christof
    36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019), 2019,
  • [27] Constructing infinite models represented by tree automata
    Nicolas Peltier
    Annals of Mathematics and Artificial Intelligence, 2009, 56 : 65 - 85
  • [28] A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance Logic
    Droste, Manfred
    PerevoshchikovS, Vitaly
    AUTOMATA, LANGUAGES, AND PROGRAMMING (ICALP 2014), PT II, 2014, 8573 : 171 - 182
  • [29] Scattering the Geometry of Weighted Graphs
    Gueneysu, Batu
    Keller, Matthias
    MATHEMATICAL PHYSICS ANALYSIS AND GEOMETRY, 2018, 21 (03)
  • [30] Scattering the Geometry of Weighted Graphs
    Batu Güneysu
    Matthias Keller
    Mathematical Physics, Analysis and Geometry, 2018, 21
12345