The finite graph problem for two-way alternating automata

Two-way alternating automata on infinite trees were introduced by Vardi (Reasoning about the part with two way automata, Lecture Notes in Computer Science, vol. 11, Springer, Berlin, 1998, pp. 628–641). Here we consider alternating two-way automata on graphs and show the decidability of the followin...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2003-04, Vol.298 (3), p.511-528
Main Author: BOJANCZYK, Mikolaj
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Alternating automata
Applied sciences
Automata. Abstract machines. Turing machines
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Finite model
General logic
Graph theory
Logic and foundations
Mathematical logic, foundations, set theory
Mathematics
Sciences and techniques of general use
Theoretical computing
μ-calculus
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Two-way alternating automata on infinite trees were introduced by Vardi (Reasoning about the part with two way automata, Lecture Notes in Computer Science, vol. 11, Springer, Berlin, 1998, pp. 628–641). Here we consider alternating two-way automata on graphs and show the decidability of the following problem: “does a given automaton with the Büchi condition accept any finite graph?” Using this result we demonstrate the decidability of the finite model problem for a certain fragment of the modal μ-calculus with backward modalities.
ISSN:0304-3975
1879-2294
DOI:10.1016/S0304-3975(02)00866-6