Alternating tree automata
The concept of alternation has been introduced by Chandra, Stockmeyer and Kozen as a natural extension of the concept of nondeterminism. The effect of alternation has been studied in the context of computational complexity, automata theory, algebra, dynamic logic and combinatorial games. This paper discusses the effect of alternation on several varieties of tree automata. In the case of top-down tree automata, alternation turns out to be equivalent to nondeterminism. In the case of two-way tree automata, alternation turns out to be more powerful than nondeterminism and alternating two-way tree automata define exactly RECOG, the class of recognizable tree languages. When the two-way tree automata are also equipped with a synchronized pushdown facility, then the alternating version is equivalent to the deterministic one.
- scientific article; zbMATH DE number 4083011
- Alternating automata on infinite trees
- Alternating two-way AC-tree automata
- scientific article; zbMATH DE number 3854429
- Tree automata
- scientific article; zbMATH DE number 168434
- L-valued alternating tree automata
- Alternating Tree Automata and Parity Games
- Alternating register automata on finite words and trees
- Iterative tree automata
- Alternation
- Bottom-up and top-down tree transformations— a comparison
- Classes of Pebble Games and Complete Problems
- Complexity of Boolean algebras
- Generalized finite automata theory with an application to a decision problem of second-order logic
- scientific article; zbMATH DE number 3814988 (Why is no real title available?)
- scientific article; zbMATH DE number 1456950 (Why is no real title available?)
- scientific article; zbMATH DE number 3301432 (Why is no real title available?)
- Parallel and two-way automata on directed ordered acyclic graphs
- Probabilistic tree automata and context free languages
- Provably Difficult Combinatorial Games
- Tree acceptors and some of their applications
- Tree transducers, L systems, and two-way machines
- The time complexity of typechecking tree-walking tree transducers
- Concurrent program schemes and their logics
- Alternating automata on infinite trees
- A grammatical characterization of alternating pushdown automata
- Top-down tree transducers with two-way tree walking look-ahead
- Synchronized tree automata
- Yield-languages of two-way pushdown tree automata
- Decision procedures for inductive Boolean functions based on alternating automata
- The finite graph problem for two-way alternating automata.
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Alternating two-way AC-tree automata
- Alternating Weighted Automata
- L-valued alternating tree automata
- Constructions for alternating finite automata∗
- An Infinite Automaton Characterization of Double Exponential Time
- scientific article; zbMATH DE number 3967934 (Why is no real title available?)
- Yield-languages recognized by alternating tree recognizers
- scientific article; zbMATH DE number 4083011 (Why is no real title available?)
- ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
- scientific article; zbMATH DE number 168434 (Why is no real title available?)
- Alternating Tree Automata and Parity Games
- An alternating hierarchy for finite automata
- scientific article; zbMATH DE number 1931697 (Why is no real title available?)
- Decidability of equivalence for deterministic synchronized tree automata
- Decidable containment of recursive queries
- Alphabetic and synchronized tree transducers
- Decidability of equivalence for deterministic synchronized tree automata
This page was built for publication: Alternating tree automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1077932)
