Labyrinth Problems Labyrinth-Searching Abilities of Automata
Corporate Author: | |
---|---|
Format: | eBook |
Language: | German |
Published: |
Wiesbaden
Vieweg+Teubner Verlag
1989, 1989
|
Edition: | 1st ed. 1989 |
Series: | Teubner-Texte zur Mathematik
|
Subjects: | |
Online Access: | |
Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
Table of Contents:
- I. Basic Concepts
- 1.1. Graphoids
- 1.2. R-graphoids
- 1.3. C-graphoids
- 1.4. The hierarchy of types of labyrinths
- 1.5. Automata in labyrinths
- 1.6. Normal labyrinth problems and reducibility
- 1.7. Finite automata in corridors
- 1.8. Vertex substitutions
- 1.9. Edge substitutions
- 1.10. Edge insertions
- II. Searching Algorithms
- 2.1. Pidgin Programming Language and Tarry’s algorithm
- 2.2. Face-following and edge-blocking
- 2.3. The bridge-preferring method
- 2.4. Modifications of bridge-preferring
- 2.5. Edge-blocking in normed 2D ficographs
- 2.6. Regular swinging in 20 ficographs
- 2.7. Searching by means of space-bounded Turing tapes
- 2.8. Searching all infinite connected 2D graphs
- III. Trap Constructions
- 3.1. Plane R-traps for finite automata and related types
- 3.2. Traps for halting automata
- 3.3. 2D traps for finite automata
- 3.4. Corollaries about 2D traps
- 3.5. Universal traps
- 3.6. Plane R-traps for plenary multihead automata
- 3.7. Barrages and traps for cooperating systems
- IV. Supplements and Problems
- 4.1. Automata without markers in finite labyrinths
- 4.2. Marker automata and cooperating systems in finite labyrinths
- 4.3. Automata in infinite labyrinths
- 4.4. On some other results and problems
- L. Labyrinth theory
- S. Surroundings
- Q. Quotations
- Theorems, corollaries, propositions, lemmas, programs supplements, problems, figures
- Definitions
- Symbols introduced within the text
- Some predefined symbols