Alternating tree automata
From MaRDI portal
Publication:1077932
DOI10.1016/0304-3975(85)90077-5zbMATH Open0595.68050OpenAlexW2115587183MaRDI QIDQ1077932FDOQ1077932
Authors: Giora Slutzki 
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
Recommendations
- scientific article; zbMATH DE number 4083011
- Alternating automata on infinite trees
- Alternating two-way AC-tree automata
- scientific article
- 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
Cites Work
- Bottom-up and top-down tree transformations— a comparison
- Alternation
- Provably Difficult Combinatorial Games
- Complexity of Boolean algebras
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Tree acceptors and some of their applications
- Parallel and two-way automata on directed ordered acyclic graphs
- Tree transducers, L systems, and two-way machines
- Title not available (Why is that?)
- Title not available (Why is that?)
- Classes of Pebble Games and Complete Problems
- Probabilistic tree automata and context free languages
- Title not available (Why is that?)
Cited In (28)
- Constructions for alternating finite automata∗
- Title not available (Why is that?)
- Decidable containment of recursive queries
- \(L\)-valued alternating tree automata
- Concurrent program schemes and their logics
- Top-down tree transducers with two-way tree walking look-ahead
- Decision procedures for inductive Boolean functions based on alternating automata
- The finite graph problem for two-way alternating automata.
- A grammatical characterization of alternating pushdown automata
- Alternating two-way AC-tree automata
- An alternating hierarchy for finite automata
- Synchronized tree automata
- Decidability of equivalence for deterministic synchronized tree automata
- The time complexity of typechecking tree-walking tree transducers
- Alternating automata on infinite trees
- Alternating Tree Automata and Parity Games
- Alternating Weighted Automata
- An Infinite Automaton Characterization of Double Exponential Time
- Yield-languages recognized by alternating tree recognizers
- Linear-bounded composition of tree-walking tree transducers: linear size increase and complexity
- ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
- Title not available (Why is that?)
- Title not available (Why is that?)
- Yield-languages of two-way pushdown tree automata
- Alphabetic and synchronized tree transducers
- XML navigation and transformation by tree-walking automata and transducers with visible and invisible pebbles
- Title not available (Why is that?)
- 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)
