Complementing unary nondeterministic automata

DOI10.1016/j.tcs.2004.04.015zbMath1078.68091OpenAlexW2081149873WikidataQ61677527 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

zbMATH Keywords

Descriptional complexityFormal languagesFinite state automataUnary languagesComplementation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

Complementing two-way finite automata ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Descriptional complexity of limited automata ⋮ Reversal of binary regular languages ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ Transition complexity of language operations ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Some results on the structure of unary unambiguous automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Note on Reversal of Binary Regular Languages ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional complexity of regular languages ⋮ On Simulation Cost of Unary Limited 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

This page was built for publication: Complementing unary nondeterministic automata