Alternation in two-way finite automata
From MaRDI portal
Publication:2029487
DOI10.1016/J.TCS.2020.12.011zbMATH Open1504.68104OpenAlexW3113059832MaRDI QIDQ2029487FDOQ2029487
Authors: Christos 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
Recommendations
Cites Work
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- Alternation
- Descriptional and computational complexity of finite automata -- a survey
- On equations for regular languages, finite automata, and sequential networks
- State-complexity of finite-state devices, state compressibility and incompressibility
- Size Complexity of Two-Way Finite Automata
- Nondeterminism and the size of two way finite automata
- Succinct representation of regular languages by Boolean automata
- Alternating finite automata and star-free languages
- Constructions for alternating finite automata∗
- An alternating hierarchy for finite automata
- Descriptional and Computational Complexity of Finite Automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Alternating Pushdown and Stack Automata
- Succinct representation of regular languages by Boolean automata. II
- On generalized language equations
- Complexity results for two-way and multi-pebble automata and their logics
- The complexity of concatenation on deterministic and alternating finite automata
- The theory of formal languages
- Operations on Boolean and alternating finite automata
- Two-way automata and length-preserving homomorphisms
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- From bidirectionality to alternation.
- 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
- Title not available (Why is that?)
- Complement for two-way alternating automata
- Probabilism versus Alternation for Automata
Cited In (14)
- One alternation can be more powerful than randomization in small and fast two-way finite automata
- From bidirectionality to alternation.
- Complement for two-way alternating automata
- Method of Constructing Two-Way Alternating Automata for PSL and Translation to Nondeterministic Automata
- Two-way automaton computations
- Accepting runs in a two-way finite automaton
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Improved complement for two-way alternating automata
- Complement for two-way alternating automata
- Existential and universal width of alternating finite automata
- Title not available (Why is that?)
- Two Grammatical Equivalents of Flip-Pushdown Automata
- Width measures of alternating finite automata
- Converting finite width AFAs to nondeterministic and universal finite automata
This page was built for publication: Alternation in two-way finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2029487)
