Complementing unary nondeterministic automata

DOI10.1016/J.TCS.2004.04.015MaRDI QIDQ1763723zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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)

Recommendations

• On complementing nondeterministic Büchi automata
• Nondeterministic multicounter machines and complementation
• Mathematical Foundations of Computer Science 2003
• On completeness of nondeterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Unary NFAs with limited nondeterminism
• Complementation, Disambiguation, and Determinization of Büchi Automata Unified
• Canonical nondeterministic automata

Cites work

• scientific article; zbMATH DE number 3657869 (Why is no real title available?)
• scientific article; zbMATH DE number 1948495 (Why is no real title available?)
• scientific article; zbMATH DE number 1502111 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 1418342 (Why is no real title available?)
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• Descriptional complexity of machines with limited resources
• Finite automata and unary languages
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the maximal order in $S_n$ and $S*_n$
• Optimal simulations between unary automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• State complexity of regular languages
• Succinct representation of regular languages by Boolean automata
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION

Cited in

(20)

• Converting Self-verifying Automata into Deterministic Automata
• Tools and Algorithms for the Construction and Analysis of Systems
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Optimal simulation of self-verifying automata by deterministic automata
• Some results on the structure of unary unambiguous automata
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Investigations on automata and languages over a unary alphabet
• Complementing two-way finite automata
• Reversal of binary regular languages
• Operational state complexity of unary NFAs with finite nondeterminism
• Descriptional complexity of limited automata
• Note on reversal of binary regular languages
• Unary NFAs with limited nondeterminism
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Descriptional complexity of regular languages
• Transition complexity of language operations
• On simulation cost of unary limited automata
• Simulations of unary one-way multi-head finite automata

This page was built for publication: Complementing unary nondeterministic automata

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