Complementing unary nondeterministic automata
From MaRDI portal
Publication:1763723
DOI10.1016/j.tcs.2004.04.015zbMath1078.68091WikidataQ61677527 ScholiaQ61677527MaRDI QIDQ1763723
Filippo Mera, Giovanni Pighizzini
Publication date: 22 February 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2004.04.015
68Q45: Formal languages and automata
Related Items
A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton, SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA, Note on Reversal of Binary Regular Languages, On Simulation Cost of Unary Limited Automata, Investigations on Automata and Languages Over a Unary Alphabet, Reversal of binary regular languages, Some results on the structure of unary unambiguous automata, Optimal simulation of self-verifying automata by deterministic automata, Operational state complexity of unary NFAs with finite nondeterminism, Descriptional complexity of limited automata, Descriptional complexity of regular languages, Pairs of complementary unary languages with ``balanced nondeterministic automata, Transition complexity of language operations, Complementing two-way finite automata, NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY, Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity, Converting Self-verifying Automata into Deterministic Automata
Cites Work
- Partial orders on words, minimal elements of regular languages, and state complexity
- Finite automata and unary languages
- Succinct representation of regular languages by Boolean automata
- Optimal Simulations between Unary Automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- On the maximal order in $S_n$ and $S*_n$
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item