Homomorphisms on graph-walking automata
From MaRDI portal
Publication:2164747
DOI10.1007/978-3-031-07469-1_14OpenAlexW3215483524MaRDI QIDQ2164747
Alexander Okhotin, Olga Martynova
Publication date: 16 August 2022
Full work available at URL: https://arxiv.org/abs/2111.10214
Cites Work
- Unnamed Item
- State complexity of operations on two-way finite automata over a unary alphabet
- On the state complexity of operations on two-way finite automata
- Tree-walking automata cannot be determinized
- A homomorphic characterization of regular languages
- Converting two-way nondeterministic unary automata into simpler automata.
- Deterministic one-way simulation of two-way deterministic finite automata over small alphabets
- State complexity of union and intersection on graph-walking automata
- Reversibility of computations in graph-walking automata
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- Two-way automata characterizations of L/poly versus NL
- Graph exploration by a finite automaton
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Automata and Labyrinths
- Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups
- Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
- Mathematical Foundations of Computer Science 2005
This page was built for publication: Homomorphisms on graph-walking automata
