Unambiguous finite automata over a unary alphabet

DOI10.1016/J.IC.2012.01.003MaRDI QIDQ418147zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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 automataunary languagesstate complexityLandau's functiontrade-offs in number of states

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Unambiguous finite automata over a unary alphabet
• Ambiguity of unary symmetric difference NFAs
• Ambiguity and structural ambiguity of symmetric difference NFAs
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• Some results on the structure of unary unambiguous automata

Cites work

• scientific article; zbMATH DE number 918133 (Why is no real title available?)
• scientific article; zbMATH DE number 3305070 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• Communication complexity method for measuring nondeterminism in finite automata
• Complementing two-way finite automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• 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$
• Optimal simulations between unary automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Ramanujan Primes and Bertrand's Postulate
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Some results on the structure of unary unambiguous automata
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
• The n -th Prime is Greater than n logn
• The Rank of Circulant Matrices
• The maximum order of an element of a finite symmetric group.
• The state complexities of some basic operations on regular languages
• The tractability frontier for NFA minimization
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Unambiguous finite automata over a unary alphabet

Cited in

(33)

• On the Size of the Universal Automaton of a Regular Language
• Ambiguity of unary symmetric difference NFAs
• State complexity of GF(2)-operations on unary languages
• Efficient construction of semilinear representations of languages accepted by unary nondeterministic finite automata
• Operations on Unambiguous Finite Automata
• Unambiguous finite automata over a unary alphabet
• Mathematical Foundations of Computer Science 2003
• Some results on the structure of unary unambiguous automata
• Ambiguity and structural ambiguity of symmetric difference NFAs
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Chrobak normal form revisited, with applications
• Unary finite automata vs. arithmetic progressions
• Worst Case Branching and Other Measures of Nondeterminism
• State complexity of operations on two-way finite automata over a unary alphabet
• Descriptional complexity of unambiguous input-driven pushdown automata
• State complexity of operations on input-driven pushdown automata
• Operations on Unambiguous Finite Automata
• On the transformation of two-way finite automata to unambiguous finite automata
• Investigations on automata and languages over a unary alphabet
• Operational state complexity of unary NFAs with finite nondeterminism
• Logarithmic asymptotics of Landau-Okhotin function
• 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
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• Unary Self-verifying Symmetric Difference Automata
• On the determinization blowup for finite automata recognizing equal-length languages
• Efficient construction of semilinear representations of languages accepted by unary NFA
• State complexity of unambiguous operations on finite automata
• Investigations on Automata and Languages over a Unary Alphabet
• Structurally Unambiguous Finite Automata
• On the state complexity of operations on two-way finite automata
• Unambiguous automata

Describes a project that uses

Uses Software

• OEIS

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

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