Investigations on Automata and Languages Over a Unary Alphabet
From MaRDI portal
Publication:5744124
DOI10.1142/S012905411540002XzbMath1330.68176MaRDI QIDQ5744124
Publication date: 17 February 2016
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Related Items
Weakly and Strongly Irreversible Regular Languages ⋮ Unnamed Item ⋮ Non-Self-Embedding Grammars and Descriptional Complexity
Cites Work
- Unnamed Item
- Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata
- Unambiguous finite automata over a unary alphabet
- State complexity of operations on two-way finite automata over a unary alphabet
- Descriptional complexity of two-way pushdown automata with restricted head reversals
- Head and state hierarchies for unary multi-head finite automata
- Some results on the structure of unary unambiguous automata
- Two-way unary automata versus logarithmic space
- Deterministic two-way one-head pushdown automata are very powerful
- The state complexity of \(L^{2}\) and \(L^k\)
- Unary finite automata vs. arithmetic progressions
- A note on bounded-reversal multipushdown machines
- The method of forced enumeration for nondeterministic automata
- Finite automata and unary languages
- A note on semilinear sets and bounded-reversal multihead pushdown automata
- Space-bounded reducibility among combinatorial problems
- The state complexities of some basic operations on regular languages
- Converting two-way nondeterministic unary automata into simpler automata.
- Complementing unary nondeterministic automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- Two-way automata characterizations of L/poly versus NL
- Pairs of complementary unary languages with ``balanced nondeterministic automata
- Magic numbers in the state hierarchy of finite automata
- Relationships between nondeterministic and deterministic tape complexities
- Complementing two-way finite automata
- Optimal Simulations between Unary Automata
- Size of Unary One-Way Multi-head Finite Automata
- UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
- Minicomplexity
- DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
- TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE
- Nondeterministic Space is Closed under Complementation
- Nondeterministic Computations in Sublogarithmic Space and Space Constructibility
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Regularity and Related Problems for Deterministic Pushdown Automata
- Bounded-reversal multihead finite automata languages
- Making Nondeterminism Unambiguous
- SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Chrobak Normal Form Revisited, with Applications
- Deterministic context free languages
- Probabilistic automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
This page was built for publication: Investigations on Automata and Languages Over a Unary Alphabet