Homomorphisms on graph-walking automata

DOI10.1007/978-3-031-07469-1_14MaRDI QIDQ2164747zbMATH OpenOpenAlexFDO

Authors Olga Martynova, Alexander Okhotin

Publication date 16 August 2022

Full work available at URL https://arxiv.org/abs/2111.10214

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A homomorphic characterization of regular languages
• Automata and Labyrinths
• Converting two-way nondeterministic unary automata into simpler automata.
• Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
• Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
• Graph exploration by a finite automaton
• scientific article; zbMATH DE number 3829283 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• On the state complexity of operations on two-way finite automata
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Reversibility of computations in graph-walking automata
• State complexity of operations on two-way finite automata over a unary alphabet
• State complexity of union and intersection on graph-walking automata
• Tight bounds for undirected graph exploration with pebbles and multiple agents
• Tree-walking automata cannot be determinized
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Two-way automata characterizations of L/poly versus NL

This page was built for publication: Homomorphisms on graph-walking automata

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