Complexity of exclusive nondeterministic finite automata

DOI10.1016/J.IC.2025.105336MaRDI QIDQ6931973zbMATH OpenFDO

Authors Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Publication date 9 September 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105336

zbMATH Keywords

acceptance modecomplexity of decidability problemsfinite automatanondeterminismsimulationsstate complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Cites work

• A lower bound technique for the size of nondeterministic finite automata
• A note on the space complexity of some decision problems for finite automata
• Alternation
• Complexity of exclusive nondeterministic finite automata
• Constructions for alternating finite automata^∗
• Descriptional and computational complexity of finite automata -- a survey
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Minicomplexity
• Minimal NFA Problems are Hard
• Nondeterminism and the size of two way finite automata
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages
• On NFAs where all states are final, initial, or both
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the unique satisfiability problem
• Operations on Boolean and alternating finite automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Space-bounded reducibility among combinatorial problems
• State complexity of unique rational operations
• Succinct representation of regular languages by Boolean automata
• The complexity theory companion

This page was built for publication: Complexity of exclusive nondeterministic finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6931973)