Operational state complexity of unary NFAs with finite nondeterminism
From MaRDI portal
Publication:896686
DOI10.1016/j.tcs.2015.07.006zbMath1332.68125OpenAlexW847683642MaRDI QIDQ896686
Alexandros Palioudakis, Kai Salomaa, Selim G. Akl
Publication date: 10 December 2015
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.006
finite automatastate complexitylimited nondeterminismdescriptional complexityunary regular languageslanguage operations
Related Items
State complexity of permutation on finite languages over a binary alphabet ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ From Parallelism to Nonuniversality: An Unconventional Trajectory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unambiguous finite automata over a unary alphabet
- Descriptional and computational complexity of finite automata -- a survey
- An optimal lower bound for the Frobenius problem
- On measuring nondeterminism in regular languages
- Finite automata and unary languages
- The state complexities of some basic operations on regular languages
- Complementing unary nondeterministic automata
- Communication complexity method for measuring nondeterminism in finite automata
- The Frobenius problem, rational polytopes, and Fourier-Dedekind sums
- Magic numbers in the state hierarchy of finite automata
- Comparisons between Measures of Nondeterminism on Finite Automata
- Unary NFAs with Limited Nondeterminism
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- State Complexity and Limited Nondeterminism
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
- The 𝑘^{𝑡ℎ} prime is greater than 𝑘(ln𝑘+lnln𝑘-1) for 𝑘≥2
- Chrobak Normal Form Revisited, with Applications
- State Complexity of Unary Language Operations for NFAs with Limited Nondeterminism
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
