Alternation in two-way finite automata
From MaRDI portal
Publication:2029487
DOI10.1016/j.tcs.2020.12.011zbMath1504.68104OpenAlexW3113059832MaRDI QIDQ2029487
Christos A. Kapoutsis, Mohammad Zakzok
Publication date: 3 June 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.12.011
Related Items (4)
Improved complement for two-way alternating automata ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ Width measures of alternating finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- An alternating hierarchy for finite automata
- Descriptional and computational complexity of finite automata -- a survey
- On equations for regular languages, finite automata, and sequential networks
- Succinct representation of regular languages by Boolean automata. II
- On generalized language equations
- Succinct representation of regular languages by Boolean automata
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Complexity results for two-way and multi-pebble automata and their logics
- The theory of formal languages
- From bidirectionality to alternation.
- Alternating finite automata and star-free languages
- Operations on Boolean and alternating finite automata
- Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday
- Square on deterministic, alternating, and Boolean finite automata
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Alternating Pushdown and Stack Automata
- Constructions for alternating finite automata∗
- Descriptional and Computational Complexity of Finite Automata
- Size Complexity of Two-Way Finite Automata
- Alternation
- Two-way automata and length-preserving homomorphisms
- The complexity of concatenation on deterministic and alternating finite automata
- State-complexity of finite-state devices, state compressibility and incompressibility
- Nondeterminism and the size of two way finite automata
- Complement for two-way alternating automata
- Probabilism versus Alternation for Automata
This page was built for publication: Alternation in two-way finite automata
