Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
From MaRDI portal
Publication:2922024
DOI10.1007/978-3-662-44522-8_25zbMath1425.68200OpenAlexW647462584WikidataQ57380760 ScholiaQ57380760MaRDI QIDQ2922024
Viliam Geffert, Alexander Okhotin
Publication date: 14 October 2014
Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-44522-8_25
Related Items (8)
A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic \(\mathcal{EL}\) ⋮ Improved complement for two-way alternating automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Complement for two-way alternating automata ⋮ Alternation in two-way finite automata ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ State complexity of union and intersection on graph-walking automata
This page was built for publication: Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
