Finite automata and unary languages

DOI10.1016/0304-3975(86)90142-8zbMath0638.68096OpenAlexW1971747251WikidataQ57380795 ScholiaQ57380795MaRDI QIDQ1099644

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90142-8

zbMATH Keywords

deterministic finite automata unary language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (only showing first 100 items - show all)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Contextual array grammars with matrix control, regular control languages, and tissue P systems control ⋮ The State Complexity of Lexicographically Smallest Words and Computing Successors ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ String theories involving regular membership predicates: from practice to theory and back ⋮ The state complexity of \(L^{2}\) and \(L^k\) ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ On the complexity of determinizing monitors ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Series parallel digraphs with loops ⋮ On the existence of prime decompositions ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ A Cookbook for Temporal Conceptual Data Modelling with Description Logics ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ Automaticity. II: Descriptional complexity in the unary case ⋮ Unnamed Item ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Towards more efficient methods for solving regular-expression heavy string constraints ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Deciding determinism of unary languages ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ Distributed graph problems through an automata-theoretic lens ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Nondeterministic state complexity of star-free languages ⋮ Geometrical regular languages and linear Diophantine equations: the strongly connected case ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Two-way automata and length-preserving homomorphisms ⋮ On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes ⋮ The Frobenius Problem and Its Generalizations ⋮ A new algorithm for regularizing one-letter context-free grammars. ⋮ DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET ⋮ Finite Automata, Palindromes, Powers, and Patterns ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ Hyper-minimizing minimized deterministic finite state automata ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ Resynchronizing Classes of Word Relations ⋮ On the expressiveness of Büchi arithmetic ⋮ Nondeterministic syntactic complexity ⋮ Magic numbers in the state hierarchy of finite automata ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata ⋮ New size hierarchies for two way automata ⋮ UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION ⋮ Non-Self-Embedding Grammars and Descriptional Complexity ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ LIMITED AUTOMATA AND REGULAR LANGUAGES ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Complementing unary nondeterministic automata ⋮ State fusion of fuzzy automata with application on target tracking ⋮ Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA ⋮ On binary circle plus operator \(\oplus\)-NFAs and succinct descriptions of regular languages ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth ⋮ On the limits of the communication complexity technique for proving lower bounds on the size of minimal NFA's ⋮ Determination of finite automata accepting subregular languages ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Unnamed Item ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ Chrobak Normal Form Revisited, with Applications ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ Geometrical Regular Languages and Linear Diophantine Equations ⋮ Remarks on Separating Words ⋮ State Complexity of Projected Languages ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ Optimal state reductions of automata with partially specified behaviors ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Determinizing monitors for HML with recursion ⋮ The descriptional power of queue automata of constant length ⋮ Reversibility for stateless ordered RRWW-automata ⋮ Static and dynamic property-preserving updates ⋮ Determinisability of unary weighted automata over the rational numbers ⋮ Size Complexity of Two-Way Finite Automata ⋮ Magic Numbers and Ternary Alphabet ⋮ Reversible Ordered Restarting Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Contextual Array Grammars with Matrix and Regular Control ⋮ Operations on Weakly Recognizing Morphisms ⋮ Descriptional Complexity of Bounded Regular Languages ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ Deterministic regular expressions with back-references ⋮ Ambiguity of Unary Symmetric Difference NFAs ⋮ Descriptional complexity of regular languages ⋮ Deterministic generalized automata ⋮ Detecting palindromes, patterns and borders in regular languages ⋮ Deterministic blow-ups of minimal NFA's ⋮ Simulating finite automata with context-free grammars. ⋮ Tight lower bounds on the size of sweeping automata ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

Cites Work

This page was built for publication: Finite automata and unary languages