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

DOI10.1016/J.TCS.2012.04.010MaRDI QIDQ443746zbMATH OpenOpenAlexWikidataFDO

Authors Michal Kunc, Alexander Okhotin

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 languagesunary languagesstate complexityLandau's functiontwo-way automata

Mathematics Subject Classification ID

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

Recommendations

• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• On the state complexity of operations on two-way finite automata
• On the State Complexity of Operations on Two-Way Finite Automata
• State complexity of unambiguous operations on finite automata
• The state complexity of \(L^{2}\) and \(L^k\)

Cites work

• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• A Stronger Bertrand's Postulate with an Application to Partitions
• Complementing two-way finite automata
• Converting two-way nondeterministic unary automata into simpler automata.
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Finite automata and unary languages
• Mathematical Foundations of Computer Science 2005
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On the State Complexity of Operations on Two-Way Finite Automata
• Optimal simulations between unary automata
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• State complexity of power
• The maximum order of an element of a finite symmetric group.
• The state complexities of some basic operations on regular languages
• The state complexity of \(L^{2}\) and \(L^k\)
• UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
• Unambiguous finite automata over a unary alphabet

Cited in

(16)

• On the State Complexity of Operations on Two-Way Finite Automata
• scientific article; zbMATH DE number 6887117 (Why is no real title available?)
• Homomorphisms and inverse homomorphisms on graph-walking automata
• Descriptional complexity of limited automata
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• Investigations on automata and languages over a unary alphabet
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Homomorphisms on graph-walking automata
• Two-way unary automata versus logarithmic space
• On simulation cost of unary limited automata
• State complexity of unambiguous operations on finite automata
• Two-Way Unary Automata versus Logarithmic Space
• 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
• State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata

This page was built for publication: State complexity of operations on two-way 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 Q443746)