Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups

DOI10.1007/978-3-642-22321-1_28zbMath1221.68157OpenAlexW2285266141WikidataQ57380797 ScholiaQ57380797MaRDI QIDQ5199977

Michal Kunc, Alexander Okhotin

Publication date: 29 July 2011

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22321-1_28

Mathematics Subject Classification ID

Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35)

Related Items (18)

Descriptional Complexity of Input-Driven Pushdown Automata ⋮ Homomorphisms on graph-walking automata ⋮ Complexity of Promise Problems on Classical and Quantum Automata ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Unambiguous finite automata over a unary alphabet ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ State complexity of operations on two-way finite automata over a unary alphabet ⋮ Reversibility of computations in graph-walking automata ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ On the Length of Shortest Strings Accepted by Two-way Finite Automata ⋮ On the state complexity of operations on two-way 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 ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ State complexity of GF(2)-operations on unary languages ⋮ Two-way automata characterizations of L/poly versus NL

This page was built for publication: Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups