Homomorphisms and inverse homomorphisms on graph-walking automata

DOI10.1016/j.tcs.2023.114197OpenAlexW4386813184MaRDI QIDQ6057839

Alexander Okhotin, Olga Martynova

Publication date: 26 October 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114197

zbMATH Keywords

homomorphismstree automatastate complexitytree-walking automatagraph-walking automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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
• Complementing deterministic tree-walking automata
• 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
• Two-way automata versus logarithmic space
• Graph exploration by a finite automaton
• Complementing two-way finite automata
• State complexity of transforming graph-walking automata to halting, returning and reversible
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Bottom-up and top-down tree transformations— a comparison
• 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 and inverse homomorphisms on graph-walking automata