Pairs of complementary unary languages with ``balanced nondeterministic automata

DOI10.1007/s00453-010-9479-9zbMath1236.68168WikidataQ61677506 ScholiaQ61677506MaRDI QIDQ2429361

Giovanni Pighizzini, Viliam Geffert

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9479-9

zbMATH Keywords

state complexity; finite state automata; unary regular languages; unary automata

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Investigations on Automata and Languages Over a Unary Alphabet, Unnamed Item, Unambiguous finite automata over a unary alphabet, Optimal state reductions of automata with partially specified behaviors, Unary Self-verifying Symmetric Difference Automata

Cites Work

• Unnamed Item
• Some results on the structure of unary unambiguous automata
• Unary finite automata vs. arithmetic progressions
• Finite automata and unary languages
• Complementing unary nondeterministic automata
• On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
• Magic numbers in the state hierarchy of finite automata
• Optimal Simulations between Unary Automata
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• The Maximum Order of an Element of a Finite Symmetric Group
• Unambiguous Finite Automata over a Unary Alphabet
• Converting Self-verifying Automata into Deterministic Automata
• On the maximal order in $S_n$ and $S*_n$
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The Largest Prime Dividing the Maximal Order of an Element of S n
• Sur l'ordre maximum d'un élément dans le groupe $S_n$ des permutations
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata