Alternating tree automata
From MaRDI portal
Publication:1077932
DOI10.1016/0304-3975(85)90077-5zbMath0595.68050OpenAlexW2115587183MaRDI QIDQ1077932
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90077-5
Related Items (15)
Synchronized tree automata ⋮ The finite graph problem for two-way alternating automata. ⋮ Alternating two-way AC-tree automata ⋮ Concurrent program schemes and their logics ⋮ Yield-languages of two-way pushdown tree automata ⋮ A grammatical characterization of alternating pushdown automata ⋮ Decision procedures for inductive Boolean functions based on alternating automata ⋮ XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles ⋮ An Infinite Automaton Characterization of Double Exponential Time ⋮ Top-down tree transducers with two-way tree walking look-ahead ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ Decidable containment of recursive queries ⋮ Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity ⋮ Decidability of equivalence for deterministic synchronized tree automata ⋮ The time complexity of typechecking tree-walking tree transducers
Cites Work
- Tree transducers, L systems, and two-way machines
- Complexity of Boolean algebras
- Probabilistic tree automata and context free languages
- Tree acceptors and some of their applications
- Provably Difficult Combinatorial Games
- Classes of Pebble Games and Complete Problems
- Alternation
- Parallel and two-way automata on directed ordered acyclic graphs
- Bottom-up and top-down tree transformations— a comparison
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Alternating tree automata
