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

DOI10.1007/978-3-642-22321-1_28MaRDI QIDQ5199977zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

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

Recommendations

• Finite-automaton transformations of strictly almost-periodic sequences
• Almost periodicity, finite automata mappings, and related effectiveness issues
• scientific article; zbMATH DE number 1354849
• Free semigroups of transformations defined by two-state automata
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Varieties of automata and transformation semigroups
• On free semigroups of automaton transformations
• scientific article; zbMATH DE number 3596255
• Two-way automata over locally finite semirings
• scientific article; zbMATH DE number 1047894

Cited in

(22)

• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
• State complexity of GF(2)-operations on unary languages
• Homomorphisms on graph-walking automata
• Reversibility of computations in graph-walking automata
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Periodic properties of pushdown automata
• Two-way automata characterizations of L/poly versus NL
• Complexity of promise problems on classical and quantum automata
• From two-way to one-way finite automata -- three regular expression-based methods
• Descriptional complexity of input-driven pushdown automata
• Unambiguous finite automata over a unary alphabet
• State complexity of operations on two-way finite automata over a unary alphabet
• Descriptional complexity of unambiguous input-driven pushdown automata
• On the state complexity of operations on two-way finite automata
• On the length of shortest strings accepted by two-way finite automata
• State complexity of operations on two-way deterministic finite automata over a unary alphabet
• Investigations on automata and languages over a unary alphabet
• Homomorphisms and inverse homomorphisms on graph-walking automata
• On the transformation of two-way finite automata to unambiguous finite automata
• Simulating two-way nondeterministic finite automata over small alphabets by one-way nondeterministic automata
• On the transformation of two-way nondeterministic finite automata to unambiguous finite automata
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199977)