On NFAs where all states are final, initial, or both

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

zbMATH Keywords

state complexityPSPACE-complete problemnondeterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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