Alternation in two-way finite automata
From MaRDI portal
Publication:2029487
Recommendations
Cites work
- Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday
- Alternating finite automata and star-free languages
- Alternating Pushdown and Stack Automata
- Alternation
- An alternating hierarchy for finite automata
- Complement for two-way alternating automata
- Complexity results for two-way and multi-pebble automata and their logics
- Constructions for alternating finite automata∗
- Descriptional and Computational Complexity of Finite Automata
- Descriptional and computational complexity of finite automata -- a survey
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- From bidirectionality to alternation.
- scientific article; zbMATH DE number 8785 (Why is no real title available?)
- Nondeterminism and the size of two way finite automata
- On equations for regular languages, finite automata, and sequential networks
- On generalized language equations
- Operations on Boolean and alternating finite automata
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Probabilism versus Alternation for Automata
- Size Complexity of Two-Way Finite Automata
- Square on deterministic, alternating, and Boolean finite automata
- State-complexity of finite-state devices, state compressibility and incompressibility
- Succinct representation of regular languages by Boolean automata
- Succinct representation of regular languages by Boolean automata. II
- The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
- The complexity of concatenation on deterministic and alternating finite automata
- The theory of formal languages
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Two-way automata and length-preserving homomorphisms
Cited in
(19)- From bidirectionality to alternation.
- Accepting runs in a two-way finite automaton
- Width measures of alternating finite automata
- Improved complement for two-way alternating automata
- One alternation can be more powerful than randomization in small and fast two-way finite automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- Method of Constructing Two-Way Alternating Automata for PSL and Translation to Nondeterministic Automata
- Two-way automaton computations
- scientific article; zbMATH DE number 1834680 (Why is no real title available?)
- Two Grammatical Equivalents of Flip-Pushdown Automata
- Complement for two-way alternating automata
- Complement for two-way alternating automata
- Converting finite width AFAs to nondeterministic and universal finite automata
- Existential and universal width of alternating finite automata
- Derivatives on graphs for the positive calculus of relations with transitive closure
- Improved upper bounds for determinizing NIDPDAs with limited nondeterminism
- Automata linear dynamic logic on finite traces
- Existential and universal width of alternating finite automata
- Maximal universal width of an AFA is NP-hard
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)
