Automata and Labyrinths

DOI10.1002/MANA.19780860120MaRDI QIDQ4191609zbMATH OpenOpenAlexFDO

Authors Lothar Budach

Publication date 1978

Published in Mathematische Nachrichten (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/mana.19780860120

zbMATH Keywords

Category of AutomataFinite AutomatonLabyrinthsMouse

Mathematics Subject Classification ID

Categories of machines, automata (18B20) Learning and adaptive systems in artificial intelligence (68T05)

Cited in

(34)

• Embedding rectilinear graphs in linear time
• State complexity of union and intersection on graph-walking automata
• Homomorphisms on graph-walking automata
• Reversibility of computations in graph-walking automata
• A tight lower bound for semi-synchronous collaborative grid exploration
• Building a nest by an automaton
• Graph decomposition for memoryless periodic exploration
• Graph exploration by a finite automaton
• A survey of two-dimensional automata theory
• State complexity of transforming graph-walking automata to halting, returning and reversible
• Graph Decomposition for Improving Memoryless Periodic Exploration
• More efficient periodic traversal in anonymous undirected graphs
• On the Power of Local Orientations
• More efficient periodic traversal in anonymous undirected graphs
• On reduction of automata in labyrinths
• Shape recognition by a finite automaton robot
• Building a nest by an automaton
• A tight lower bound for semi-synchronous collaborative grid exploration
• Energy consumption of group search on a line
• Memory Efficient Anonymous Graph Exploration
• Homomorphisms and inverse homomorphisms on graph-walking automata
• Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
• A time to cast away stones
• Tight bounds for deterministic high-dimensional grid exploration
• Graph exploration by a deterministic memoryless automaton with pebbles
• Exploration of convex terrains by a deterministic automaton with pebbles
• A time to cast away stones: on a family of pebble automata
• Exploring wedges of an oriented grid by an automaton with pebbles
• Lower bounds for graph-walking automata
• State complexity of Boolean operations on graph-walking automata
• Fast periodic graph exploration with constant memory
• Setting port numbers for fast graph exploration
• Impact of memory size on graph exploration capability
• Anonymous graph exploration without collision by mobile robots

This page was built for publication: Automata and Labyrinths

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