State complexity of operations on two-way finite automata over a unary alphabet

DOI10.1016/j.tcs.2012.04.010zbMath1255.68078OpenAlexW2095117965WikidataQ57380777 ScholiaQ57380777MaRDI QIDQ443746

Alexander Okhotin, Michal Kunc

Publication date: 13 August 2012

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.04.010

zbMATH Keywords

finite automataregular languagesstate complexityunary languagesLandau's functiontwo-way automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items (11)

Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Descriptional complexity of limited automata ⋮ A Superpolynomial Lower Bound for the Size of Non-Deterministic Complement of an Unambiguous Automaton ⋮ On the state complexity of operations on two-way finite automata ⋮ Quantum finite automata: advances on Bertoni's ideas ⋮ SIMULATIONS OF UNARY ONE-WAY MULTI-HEAD FINITE AUTOMATA ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ State Complexity of Operations on Two-Way Deterministic Finite Automata over a Unary Alphabet ⋮ On Simulation Cost of Unary Limited Automata ⋮ State complexity of unambiguous operations on finite automata

Cites Work

• Unnamed Item
• Unambiguous finite automata over a unary alphabet
• The state complexity of \(L^{2}\) and \(L^k\)
• State complexity of power
• Finite automata and unary languages
• The state complexities of some basic operations on regular languages
• Converting two-way nondeterministic unary automata into simpler automata.
• Complementing two-way finite automata
• Optimal Simulations between Unary Automata
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• On the State Complexity of Operations on Two-Way Finite Automata
• The Maximum Order of an Element of a Finite Symmetric Group
• 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
• Mathematical Foundations of Computer Science 2005
• A Stronger Bertrand's Postulate with an Application to Partitions
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES

This page was built for publication: State complexity of operations on two-way finite automata over a unary alphabet