Unambiguous finite automata over a unary alphabet
From MaRDI portal
Publication:418147
DOI10.1016/J.IC.2012.01.003zbMATH Open1280.68118DBLPjournals/iandc/Okhotin12OpenAlexW2082934005WikidataQ57380783 ScholiaQ57380783MaRDI QIDQ418147FDOQ418147
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
Recommendations
ambiguityfinite automataunary languagesstate complexityLandau's functiontrade-offs in number of states
Cites Work
- The state complexities of some basic operations on regular languages
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Ramanujan Primes and Bertrand's Postulate
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Title not available (Why is that?)
- The tractability frontier for NFA minimization
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Complementing two-way finite automata
- Title not available (Why is that?)
- Communication complexity method for measuring nondeterminism in finite automata
- Pairs of complementary unary languages with ``balanced nondeterministic automata
- Optimal simulations between unary automata
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- 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 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
- Some results on the structure of unary unambiguous automata
- Title not available (Why is that?)
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- The n -th Prime is Greater than n logn
- Partial orders on words, minimal elements of regular languages, and state complexity
Cited In (33)
- On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages
- Ambiguity of unary symmetric difference NFAs
- State complexity of GF(2)-operations on unary languages
- A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton
- 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
- DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
- Ambiguity and structural ambiguity of symmetric difference NFAs
- Chrobak normal form revisited, with applications
- Investigations on Automata and Languages Over a Unary Alphabet
- 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
- Logarithmic asymptotics of Landau-Okhotin function
- Operational state complexity of unary NFAs with finite nondeterminism
- 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
- 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
- On the Size of the Universal Automaton of a Regular Language
Uses Software
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)
