Unambiguous finite automata over a unary alphabet

DOI10.1016/j.ic.2012.01.003zbMath1280.68118OpenAlexW2082934005WikidataQ57380783 ScholiaQ57380783MaRDI QIDQ418147

Alexander Okhotin

Publication date: 24 May 2012

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2012.01.003

zbMATH Keywords

ambiguityfinite automatastate complexityunary languagesLandau's functiontrade-offs in number of states

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (17)

State complexity of operations on input-driven pushdown automata ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Logarithmic asymptotics of Landau-Okhotin function ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ Operations on Unambiguous Finite Automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Operations on Unambiguous Finite Automata ⋮ State complexity of unambiguous operations on finite automata ⋮ Worst Case Branching and Other Measures of Nondeterminism ⋮ State complexity of GF(2)-operations on unary languages

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The tractability frontier for NFA minimization
• Some results on the structure of unary unambiguous automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• The state complexities of some basic operations on regular languages
• Communication complexity method for measuring nondeterminism in finite automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Complementing two-way finite automata
• Optimal Simulations between Unary Automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Ramanujan Primes and Bertrand's Postulate
• The Rank of Circulant Matrices
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata
• The Maximum Order of an Element of a Finite Symmetric Group
• Unambiguous Finite Automata over a Unary Alphabet
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• On the maximal order in $S_n$ and $S*_n$
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• The n -th Prime is Greater than n logn

This page was built for publication: Unambiguous finite automata over a unary alphabet