On NFAs where all states are final, initial, or both
From MaRDI portal
Publication:1034621
DOI10.1016/j.tcs.2009.07.049zbMath1194.68140OpenAlexW1532642937MaRDI QIDQ1034621
Jui-Yi Kao, Narad Rampersad, Jeffrey O. Shallit
Publication date: 6 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2009.07.049
Related Items
STATE COMPLEXITY OF CODE OPERATORS ⋮ THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES ⋮ Quotient complexity of closed languages ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Detectability in stochastic discrete event systems ⋮ The different shades of infinite session types ⋮ Simulation by Rounds of Letter-to-Letter Transducers ⋮ Unnamed Item ⋮ Selective monitoring ⋮ Verification of initial-state opacity in security applications of discrete event systems ⋮ Decision problems for convex languages ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Determination of finite automata accepting subregular languages ⋮ On the mortality problem: from multiplicative matrix equations to linear recurrence sequences and beyond ⋮ On finite monoids over nonnegative integer matrices and short killing words ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond ⋮ State Complexity of Prefix Distance of Subregular Languages ⋮ Nondeterministic complexity in subclasses of convex languages ⋮ Descriptional complexity of regular languages ⋮ On Nonnegative Integer Matrices and Short Killing Words ⋮ Comparison of max-plus automata and joint spectral radius of tropical matrices ⋮ Square on Ideal, Closed and Free Languages
Cites Work
- Partial orders on words, minimal elements of regular languages, and state complexity
- Some remarks on multiple-entry finite automata
- State complexity of some operations on binary regular languages
- Multiple-entry finite automata
- Decision Problems for Convex Languages
- Nondeterminism and the size of two way finite automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item