State complexity of union and intersection on graph-walking automata
From MaRDI portal
Publication:2096590
DOI10.1007/978-3-030-93489-7_11OpenAlexW4206476018MaRDI QIDQ2096590
Olga Martynova, Alexander Okhotin
Publication date: 9 November 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-93489-7_11
Related Items
Homomorphisms on graph-walking automata ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
Cites Work
- Unnamed Item
- Partial orders on words, minimal elements of regular languages, and state complexity
- Complementing deterministic tree-walking automata
- Halting space-bounded computations
- Graph-walking automata: from whence they come, and whither they are bound
- Reversibility of computations in graph-walking automata
- Operational state complexity of nested word automata
- Graph exploration by a finite automaton
- Complementing two-way finite automata
- Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
- State Complexity of Union and Intersection for Two-way Nondeterministic Finite Automata
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Automata and Labyrinths
- Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Complement for two-way alternating automata
This page was built for publication: State complexity of union and intersection on graph-walking automata
