Existential and universal width of alternating finite automata
From MaRDI portal
Publication:6175087
DOI10.1007/978-3-031-34326-1_4MaRDI QIDQ6175087
Yo-Sub Han, Sung-Min Kim, Sang-Ki Ko, Kai Salomaa
Publication date: 17 August 2023
Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)
decidabilityspace complexitymeasure of nondeterminismalternating finite automatonuniversal and existential choices
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- An alternating hierarchy for finite automata
- Ambiguity and communication
- Descriptional and computational complexity of finite automata -- a survey
- Alternating finite automata with limited universal branching
- Limitedness theorem on finite automata with distance functions: An algebraic proof
- On measuring nondeterminism in regular languages
- Limitedness theorem on finite automata with distance functions
- On the power of alternation in automata theory
- Succinct representation of regular languages by Boolean automata
- On the degree of ambiguity of finite automata
- On finite automata with limited nondeterminism
- Communication complexity method for measuring nondeterminism in finite automata
- The limitedness problem on distance automata: Hashiguchi's method revisited
- Alternation in two-way finite automata
- Combining limited parallelism and nondeterminism in alternating finite automata
- Width measures of alternating finite automata
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Structural properties of NFAs and growth rates of nondeterminism measures
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Constructions for alternating finite automata∗
- A Second Course in Formal Languages and Automata Theory
- Alternation
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- State Complexity of Finite Tree Width NFAs
- Worst Case Branching and Other Measures of Nondeterminism
- Ambiguity, Nondeterminism and State Complexity of Finite Automata
This page was built for publication: Existential and universal width of alternating finite automata