Optimal Simulations between Unary Automata

Related Items (46)

Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds. ⋮ Iterated uniform finite-state transducers on unary languages ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ Converting two-way nondeterministic unary automata into simpler automata. ⋮ Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions ⋮ Unambiguous finite automata over a unary alphabet ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Binary coded unary regular languages ⋮ Descriptional complexity of limited automata ⋮ Nondeterministic state complexity of star-free languages ⋮ An alternating hierarchy for finite automata ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ TESTING THE DESCRIPTIONAL POWER OF SMALL TURING MACHINES ON NONREGULAR LANGUAGE ACCEPTANCE ⋮ A Space Lower Bound for Acceptance by One-Way Π₂-Alternating Machines ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ Hyper-minimizing minimized deterministic finite state automata ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ Iterated uniform finite-state transducers on unary languages ⋮ On the state complexity of operations on two-way finite automata ⋮ Removing nondeterminism in constant height pushdown automata ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ 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 ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Pushdown automata and constant height: decidability and bounds ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Deterministic Pushdown Automata and Unary Languages ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ The descriptional power of queue automata of constant length ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES ⋮ Descriptional complexity of regular languages ⋮ On Simulation Cost of Unary Limited Automata ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ State complexity of GF(2)-operations on unary languages ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

This page was built for publication: Optimal Simulations between Unary Automata