Complementing unary nondeterministic automata

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

zbMATH Keywords

Descriptional complexity; Formal languages; Finite state automata; Unary languages; Complementation

Mathematics Subject Classification ID

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