Labyrinth Problems

Frontmatter

Introduction

Abstract

Already since the earliest eras of civilization,the idea of mazes or labyrinths has been well-known,and they have often been used to allegorize complicated or mysterious things and hardly solvable problems.

Armin Hemmerling

Chapter I. Basic Concepts

Abstract

In this chapter we introduce the basic types of labyrinths, the automata able to operate on those,and the problems we shall deal with in the sequel. Moreover,some fundamental facts concerning these concepts are summarized.

Armin Hemmerling

Chapter II. Searching Algorithms

Abstract

In this chapter the fundamental searching algorithms for connected,especially for finite connected,R- and C-graphs are discussed. They are mainly given by programs written in Pidgin Programming Language (PPL). The algorithms are shown to be correct, the types of automata able to implement them are characterized, and the corresponding time complexities are estimated.

Armin Hemmerling

Chapter III. Trap Constructions

Abstract

Here we present unsolvability results of searching problems. They are obtained by suitable trap constructions.

Armin Hemmerling

Chapter IV. Supplements and Problems

Abstract

The aim of this fragmentary last chapter is to complete our survey of labyrinth research by reporting some further results both on searching problems and on other questions connected with, labyrinths and by stating some open problems which seem to be important for progress in research.

Armin Hemmerling

Backmatter