Complexity of exclusive nondeterministic finite automata

DOI10.1007/978-3-031-34326-1_9OpenAlexW4381855984MaRDI QIDQ6175094

Martin Kutrib, Andreas Malcher, Matthias Wendlandt

Publication date: 17 August 2023

Published in: Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-34326-1_9

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• A lower bound technique for the size of nondeterministic finite automata
• On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages
• Succinct representation of regular languages by Boolean automata
• Intersection and union of regular languages and state complexity
• Space-bounded reducibility among combinatorial problems
• On the unique satisfiability problem
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Alternation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Minimal NFA Problems are Hard
• 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
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• The complexity theory companion

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