PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 101(115) (2017), 47–63 https://doi.org/10.2289/PIM1715047K

ON REDUCTION OF AUTOMATA IN LABYRINTHS

Goran Kilibarda

Abstract. It is shown that every automaton acceptable for rectangular labyrinths can be reduced to an automaton that behaves according to either the left-hand rule or the right-hand rule, or does not move at all, in every plane rectangular labyrinth without leaves. This enables us to approach certain fundamental problems of the theory of automata in labyrinths in a quite different way.

1. Introduction

In the past fifty years much attention has been devoted to research dealing with automata analysis of geometric environment, images, graphs, formal languages and other discrete structures. The obtained results enabled the formation of a new direction in automata theory, namely, the behavior of automata in labyrinths.

Shannon’s paper on maze-solving machine [1] played an important role in the formation of the direction and outlined the range of research problems for the coming years. There he considers a model of a mouse, presented as an automaton, which should find a certain target in a maze.

One of the fundamental problems in the theory of automata in labyrinths is the question of existence of a perfect trap for an arbitrary finite automaton acceptable for rectangular labyrinths (the difference between mazes and mosaic labyrinth is negligible here). Intuitively it was clear that the answer to the question is positive, but the problem turned out to be far from simple and easy. The proof of the corresponding theorem was first given in [2], then it was considerably shortened in [6] chiefly by passing from the clear algebraic language in [2] to the language of the theory of automata in [6]. An altogether different solution of the problem was presented in [5].

Developing the ideas from [5], in this paper, we approach this and similar problems in a new way: while [2, 6] focused on the construction of the trap, here we focus on automata and prove that every automaton can be reduced to an automaton whose behavior in every plane rectangular labyrinth without leaves follows either the left-hand or the right-hand rule (when an automaton finds itself in a vertex of such a labyrinth, it always chooses the direction of its further movement which is the first either to the left or to the right, respectively, of the direction by which it reached the vertex), or does not move in it at all. By reduction we mean simplification of the automaton behavior. This reduction is done in such a way that for every given automaton 𝔄 we can construct the corresponding two basic “blocks” (also in the form of plane rectangular labyrinths) with which we can replace all the edges in an arbitrary plane rectangular labyrinth L so that the behavior of 𝔄 in thus obtained labyrinth, in respect to the vertices of L, is equivalent to the behavior of the corresponding reduced automaton in L. The above mentioned equivalence of behaviors allows us to approach some fundamental problems in the theory of automata in labyrinths in a considerably simpler way, because actually we reduce some of these problems to the corresponding problems for thus obtained reduced automata. The advantage of this method is illustrated with the proof of a theorem which is similar to the above mentioned theorem from [2, 6], but for plane rectangular labyrinths.

2010 Mathematics Subject Classification: 68Q99.

Key words and phrases: automaton, labyrinth, behavior of automata in labyrinths.

Communicated by Žarko Mijajlović.

The paper is self-contained, but one can find the basic notions and the basic results in the theory of automata in labyrinths in [3, 4], where there is also a more or less complete list of literature on this theory.

2. Automata and labyrinths

Denote the power set of a set X by P(X), and let P_{0}(X) = P(X) ∖ {∅}. Let X_{1}, …, X_{n} be arbitrary sets. For every 1 ⩽ i ⩽ n, by pr_{i} denote the projection map of the Cartesian product X_{1} × ⋯× X_{n} onto X_{i}. Denote the set of all words over an alphabet A by A^{∗}; by Λ denote the empty word.

Let 𝔇 = \{e, n, w, s\}. Take that e^{−1} = \overline{e} = w, n^{−1} = \overline{n} = s, w^{−1} = \overline{w} = e, and s^{−1} = \overline{s} = n. The elements of the set 𝔇 can be interpreted as the cardinal points: east, north, west, and south. If α = ω_{1} …ω_{n} ∈ 𝔇^{∗}, then α^{−1} = ω_{n}^{−1} …ω_{1}^{−1} ; certainly, Λ^{−1} = Λ.

A connected edge-labeled symmetric simple digraph (L, f), L = (V, E), where V is the set of vertices, E is the set of edges and f: E → 𝔇 is an edge labeling of L, is a rectangular labyrinth (or simply a labyrinth) if f[(y, x)] = (f[(x, y)])^{−1} for every (x, y) ∈ E, and if f(u) ≠ f(v) for every u, v ∈ E such that u ≠ v and pr_{1}(u) = pr_{1}(v).

Let |u|_{L} = f(u) for each u ∈ E. Also, let [x]_{L} = {|u|_{L} | pr_{1}(u) = x, u ∈ E} for every x ∈ V. If it is clear from the context what labyrinth L is meant, then instead of |u|_{L} and [x]_{L} we write |u| and [x] respectively. Adding to 𝔇 the element which we denote by 0 (the corresponding interpretation of this element will be given in the sequel), extend the definition of f on the pairs (x, x), x ∈ V, taking that |(x, x)| = 0.

Further on, we shall omit f in the designation of a labyrinth (L, f) considering that in every concrete case f is determined. Sometimes, the set of all vertices and the set of all edges of a labyrinth L are labeled by V (L) and E(L) respectively.

A labyrinth L is finite if V (L) is a finite set; otherwise L is infinite. All labyrinths in the sequel will be finite if it is not stated otherwise.

Let L be a labyrinth. Instead of L we write (L; x′) (or (V, E; x′)) [(L; x′, x′′) (or (V, E; x′, x′′))] if in L a vertex x′ [two different vertices x′ and x′′] is marked [are marked] as the entrance [the entrance and the exit]; such vertices x′ and x′′ are sometimes denoted by x_{s}(L) and x_{f}(L) respectively. If L is a labyrinth with an entrance x′ and an exit x′′, then by L^{−1} we denote the same labyrinth, but with the entrance x′′and the exit x′.

Suppose that L is a labyrinth and ρ = x_{0}, u_{1}, x_{1}, …, u_{n}, x_{n} is a walk in L. Then by |ρ| we denote the word |u_{1}| …|u_{n}|. Let x be a vertex of the labyrinth L and let α ∈ 𝔇^{∗}. If in L there exists a walk ρ starting at x such that |ρ| = α, then by (xα)_{L} we denote the end vertex of ρ. Let us take that xΛ = x for every x ∈ V (L). If it is clear from the context what labyrinth L is meant, then in the sequel we often write xα instead of (xα)_{L}.

Let L be a labyrinth. Replacing each pair of opposite edges in L with the corresponding non-labeled undirected edge, we obtain an undirected graph G(L). A labyrinth L is a tree if the graph G(L) is a tree. A labyrinth (L; x′, x′′) is an ω_{1}ω_{2}-tree, ω_{1}, ω_{2} ∈ 𝔇, if L is a tree, [x′] = \{ω_{1}\}, and [x′′] = \{\overline{ω_{2}} \}; if ω_{1} = ω_{2} = ω, then an ω_{1}ω_{2}-tree L is called an ω-tree. A labyrinth L is a labyrinth without leaves if G(L) has no leaves.

Let M and N, M ≠ N, be some points of the plane. By \overline{MN} denote the line segment which is defined by the given points, and by |\overline{MN} | its length. Let i and j be the unit vectors in the direction of the x-axis and y-axis of the rectangular coordinate system respectively. The vector \overrightarrow{MN} = α_{1}i + α_{2}j goes in the direction:

1) e if α_{1} > 0 and α_{2} = 0; 2) n if α_{1} = 0 and α_{2} > 0; 3) w if α_{1} < 0 and α_{2} = 0; and 4) s if α_{1} = 0 and α_{2} < 0.

A set T of line segments in the plane R^{2} is called a configuration (of line segments) if any two different line segments of the set T can have not more than one common point, and if such a point exists, it must be an end point for both the line segments. A labyrinth L = (V, E), V ⊆ R^{2}, is plane if the set of line segments T = \{\overline{xy} | (x, y) ∈ E\} is a configuration and the vector \overrightarrow{xy} goes in the direction |(x, y)| for every (x, y) ∈ E. If L is a plane, and, in addition, it holds that |\overline{xy}| = 1 for every (x, y) ∈ E, then we say that L is a mosaic labyrinth. Moreover, a mosaic labyrinth M is a maze if it satisfies that for every x, y ∈ V (M) from |\overline{xy}| = 1, it follows that (x, y) ∈ E(M).

For every plane labyrinth L, the set \overline{L} = ⋃ _{(x,y)∈E(L)} \overline{xy} is the (geometric) realization of a L. A plane labyrinth L is bounded if diam \overline{L} < ∞; otherwise it is unbounded.

Labyrinths L_{1} and L_{2} are called isomorphic, L_{1} ≅ L_{2}, if there exists a bijective function g: V (L_{1}) → V (L_{2}) such that:

(1) g is an isomorphism of edge-labeled digraphs L_{1} and L_{2}, i.e., (x, y) ∈ E(L_{1}) iff (g(x), g(y)) ∈ E(L_{2}) for every x, y ∈ V (L_{1}), and |(x, y)|_{L_{1}} = |(g(x), g(y))|_{L_{2}} for every (x, y) ∈ E(L_{1});

(2) if one of the labyrinths has an entrance [an entrance and an exit], then the other of them has an entrance [an entrance and an exit], too, and x_{s}(L_{2}) = g[x_{s}(L_{1})] [x_{s}(L_{2}) = g[x_{s}(L_{1})] and x_{f}(L_{2}) = g[x_{f}(L_{1})]].

Such a function g is called an isomorphism from L_{1} to L_{2}. The set of all labyrinths isomorphic to a labyrinth L is denoted by [L].

A plane [mosaic] labyrinth (L; x′, x′′) is regular [perfect ] if there exists an unbounded plane [mosaic] labyrinth L_{1} such that \overline{L} ∩ \overline{L_{1}} = \{x′′\} and x′′∈ V (L_{1}).

By automaton 𝔄 we mean a quintuple (A, Q, B, φ, ψ), where the finite nonempty sets A, Q and B are the input alphabet, the set of states and the output alphabet of the automaton respectively, ψ: Q × A → B is its output function and φ: Q × A → Q is its state-transition function. If a state q_{0} is marked in Q, we get an initial automaton 𝔄_{q_{0}} = (A, Q, B, φ, ψ, q_{0}) (in other words, 𝔄_{q_{0}} is a Mealy machine). For the given initial or non-initial automaton 𝔄, we sometimes denote the input alphabet, the set of states, the output function, the output function, and the transition function by A_{𝔄}, Q_{𝔄}, B_{𝔄}, φ_{𝔄}, and ψ_{𝔄} respectively.

An automaton (initial or non-initial) 𝔄 is said to be acceptable if A_{𝔄} = P(𝔇), B_{𝔄} = 𝔇 ∪ {0} and ψ_{𝔄} (q, a) ∈ a ∪ {0} for all q ∈ Q_{𝔄} and a ∈ A_{𝔄}. In the sequel, all automata will be acceptable, and because of that we just say ‘automaton’ instead of ‘acceptable automaton’ for the sake of brevity. An automaton 𝔄 is trivial if ψ_{𝔄} (q, a) = 0 for every q ∈ Q_{𝔄} and a ∈ P(𝔇).

Let L = (V, E; x_{0}) be a labyrinth and 𝔄_{q_{0}} = (A, Q, B, φ, ψ, q_{0}) be an initial automaton.

A sequence (q_{0}, x_{0}), (q_{1}, x_{1}), … in Q×V is called the behavior of the automaton 𝔄_{q_{0}} in the labyrinth (L; x_{0}), and it is denoted by π(𝔄_{q_{0}}; L), if for every i ⩾ 0 it holds that (x_{i}, x_{i+1} ) ∈ E or x_{i} = x_{i+1} , q_{i+1} = φ(q_{i}, [x_{i}]) and ψ(q_{i}, [x_{i}]) = |(x_{i}, x_{i+1} )|; the sequence τ(𝔄_{q_{0}}; L) = x_{0}, x_{1}, … is the trajectory of 𝔄_{q_{0}} in L. Let π_{i}(𝔄_{q_{0}}; L) = (q_{i}, x_{i}) for each i ⩾ 0. If L has also an exit y_{0} and x_{i} = y_{0} for some i ⩾ 1, then we say that 𝔄_{q_{0}} goes out of the labyrinth (L; x_{0}, y_{0}); otherwise we say that (L; x_{0}, y_{0}) is a trap for 𝔄_{q_{0}}. If 𝔄_{q_{0}} goes out of (L; x_{0}, y) for every y ∈ V ∖ {x_{0}}, we say that 𝔄_{q_{0}} searches (L; x_{0}).

Let V′ ⊆ V. If all the pairs (q_{i}, x_{i}) for which x_{i} ∉ V′ are thrown out of π(𝔄_{q_{0}}; L), we get ether a finite (empty or non-empty), or infinite sequence (q_{i_{0}} , x_{i_{0}} ), (q_{i_{1}} , x_{i_{1}} ), … which is called the V′-behavior of 𝔄_{q_{0}} in (L; x_{0}). The sequence x_{i_{0}} , x_{i_{1}} , … is the V′-trajectory of 𝔄_{q_{0}} in (L; x_{0}). It is clear that π(𝔄_{q_{0}}; L) [τ(𝔄_{q_{0}}; L)] is the V -behavior [V -trajectory] of 𝔄_{q_{0}} in (L; x_{0}).

For every V_{1} ⊆ V, determine the values st(π, V_{1}), pl(π, V_{1}), dr(π, V_{1}), tm(π, V_{1}), dr_{0}(π, V_{1}) and st_{0}(π, V_{1}), where π = π(𝔄_{q_{0}}; L), in the following way. If there exists t > 0 such that x_{t} ∈ V_{1} and x_{t′} ∉ V_{1} for every 0 < t′ < t, then st(π, V_{1}) = q_{t}, pl(π, V_{1}) = x_{t}, dr(π, V_{1}) = ψ(q_{t}, [x_{t}]_{L}) and tm(π, V_{1}) = t; otherwise st(π, V_{1}), pl(π, V_{1}), dr(π, V_{1}) are not determined and tm(π, V_{1}) = +∞. If st(π, V_{1}) is determined and if there exists the number

i_{0} = min{i ∈ N | i ⩾ tm(π, V_{1}) ∧ |(x_{i}, x_{i+1} )| ≠ 0},

then let dr_{0}(π, V_{1}) = |(x_{i_{0}} , x_{i_{0} +1} )| and st_{0}(π, V_{1}) = q_{i_{0}} . By \overline{dr}(π, t) denote the superword |(x_{t}, x_{t+1} )||x_{t+1} , x_{t+2} )| . . .. Also, by \overline{dr}_{0}(π, t) denote the superword which results from the superword \overline{dr}(π, t) by replacing all the appearances of the one-letter subword 0 by the empty word.

Let 𝔄_{1} and 𝔄_{2} be initial automata, and let (L_{1}; x′_{1}) and (L_{2}; x′_{2}) be labyrinths. For a V_{1} ⊆ V (L_{1}), let (q_{i_{0}}^{(1)}, x_{i_{0}}^{(1)}), (q_{i_{1}}^{(1)}, x_{i_{1}}^{(1)}), … be the V_{1}-behavior of 𝔄_{1} in L_{1}, and for a V_{2} ⊆ V (L_{2}), let (q_{j_{0}}^{(2)}, x_{j_{0}}^{(2)}), (q_{j_{1}}^{(2)}, x_{j_{1}}^{(2)}), … be the V_{2}-behavior of 𝔄_{2} in L_{2}. We say that the V_{1}-behavior of 𝔄_{1} in L_{1} and the V_{2}-behavior of 𝔄_{2} in L_{2} are isomorphic if: 1) for every k ⩾ 0, (q_{i_{k}}^{(1)}), x_{i_{k}}^{(1)}) exists iff (q_{j_{k}}^{(2)}, x_{j_{k}}^{(2)}) exists; and 2) there exist bijections g: Q_{𝔄_{1}} → Q_{𝔄_{2}} and h: V_{1} → V_{2} such that (g(q_{i_{m}}^{(1)}), h(x_{i_{m}}^{(1)})) = (q_{j_{m}}^{(2)}, x_{j_{m}}^{(2)}) for every m ⩾ 0 satisfying that (q_{i_{m}}^{(1)}), x_{i_{m}}^{(1)}) exists. For example, for every initial automaton 𝔄_{q_{0}}, if (L_{1}; x′_{1}) ≅ (L_{2}; x′_{2}), then π(𝔄_{q_{0}}; L_{1}) and π(𝔄_{q_{0}}; L_{2}) are isomorphic.

As the behaviors of an automaton in isomorphic labyrinths are isomorphic and, consequently, as it is not important for the problems, we investigate here which of isomorphic labyrinths is taken, we do not differentiate isomorphic labyrinths and we adopt the following convention. In the sequel, we introduce some binary operations on labyrinths, which are partially defined and which satisfy the following condition: if ∗ is one of such operations, and L_{1} and L_{2} some labyrinths, then the labyrinth [edge-labeled digraph] L ∗ L′ belongs to the same class of isomorphic labyrinths [edge-labeled digraphs] [L_{1} ∗ L_{2}] for every L ∈ [L_{1}] and L′ ∈ [L_{2}] for which it is defined. In fact, we will consider these operations as operations on the corresponding classes of isomorphic labyrinths, and when we say ‘given a labyrinth [edge-labeled digraph] L_{1} ∗ L_{2}’ we mean, in fact, that is given a labyrinth [edge-labeled digraph] from the class [L_{1}∗L_{2}], and, consequently, the result of the application of operation ∗ may exist even in the case when L_{1} ∗ L_{2} does not exist.

If by applying some operation on some labyrinths the new edges do not appear and we do not change the original labels of the remaining edges which they had in given labyrinths, we do not describe the edge labeling function of the resulting labyrinth [edge-labeled digraph] for the sake of shortness.

Let L_{1} =(V_{1}, E_{1}) and L_{2} =(V_{2}, E_{2}) be arbitrary labyrinths such that V_{1}∩V_{2} = ∅. By L_{1} ˙∪L_{2} denote the disjoint union of labyrinths L_{1} and L_{2}, i.e., L_{1} ˙∪L_{2} = (V_{1} ∪ V_{2}, E_{1} ∪ E_{2}).

Let L be a labyrinth, and let x and y, x ≠ y, be its vertices (not obviously adjacent). Denote the labyrinth (V (L), E(L) ∖ {(x, y), (y, x)}) by L − ⟨x, y⟩. If x and y are not adjacent, and [x] ∩ [y] = ∅, then by vi(L, x, y) denote the labyrinth (V ∖\{y\}, [E∖((\{y\}×V)∪(V ×\{y\}))]∪\overleftarrow{E} (x, y)∪\overrightarrow{E} (x, y)), where\overleftarrow{E} (x, y) = \{(yω, x) | ω ∈ [y]\}, \overrightarrow{E} (x, y) = \{(x, yω) | ω ∈ [y]\}, and |(x, yω)| = ω and |(yω, x)| = \overline{ω} for every ω ∈ [y] (we do not change the labels of the other edges).

Let L and (L_{1}; x′_{1}, x′′_{1}) be labyrinths such that V (L)∩V (L_{1}) = ∅, and let x and y be different vertices of L. Suppose that [x]_{L−⟨x,y⟩} ∩[x′_{1}]_{L_{1}} = [y]_{L−⟨x,y⟩} ∩[x′′_{1}]_{L_{1}} = ∅. By L_{x}+_{y} L_{1} denote the labyrinth vi(vi((L − ⟨x, y⟩) ˙∪L_{1}, x, x′_{1}), y, x′′_{1}). The idea of the described operation is the following: labyrinth L_{1} is “put” in L between the vertices x and y.

Let (L_{1}; x′_{1}, x′′_{1}) and (L_{2}; x′_{2}, x′′_{2}) be labyrinths such that V (L_{1}) ∩ V (L_{2}) = ∅ and [x′′_{1}]_{L_{1}} ∩ [x′_{2}]_{L_{2}} = ∅. Denote the labyrinth (vi(L_{1} ˙∪L_{2}, x′′_{1}, x′_{2}); x′_{1}, x′′_{2}) by L_{1}L_{2}. For given labyrinths (L_{i}; x′_{i}, x′′_{i}), 1 ⩽ i ⩽ n, by L_{1} …L_{n} denote the expression (…((L_{1}L_{2})L_{3}) …L_{n−1} )L_{n}; denote the entrance x′_{1} [the exit x′′_{n}] of this labyrinth by (L_{1} …L_{n}; 0) [(L_{1} …L_{n}; n)], and for every 1 ⩽ i ⩽ n−1, by (L_{1} …L_{n}; i) denote, now in L_{1} …L_{n}, the vertex x′′_{i}. If L_{1} ≅ ⋯≅ L_{n} ≅ L, we can write L^{n} instead of L_{1} …L_{n} (see the above convention).

For every a ∈ P_{0}(𝔇), let V′(a) = {x_{ω} | ω ∈ a}, V (a) = {x_{0}} ∪ V′(a) and E(a) = (a × {x_{0}}) ∪ ({x_{0}} × a). By L(a) denote the labyrinth (V (a), E(a); x_{0}) for which it holds that (|(x_{0}, x_{ω})|, |(x_{ω} , x_{0})|) = (ω, \overline{ω}) for all ω ∈ a. For brevity, let ⟨ω⟩ = L({ω}) for every ω ∈ 𝔇.

For every word α ∈ 𝔇^{∗} by ν(α) denote the word obtained from α by replacing in it, until it is possible, each subword of the form ωω^{−1} , ω ∈ 𝔇, with the empty word (for example, if α = wwnsesnn , then ν(α) = wn). A nonempty word α ∈ 𝔇^{∗} is a simple word over 𝔇 if α = ν(α); by Sim(𝔇) denote the set of all simple words over 𝔇. For every α = ω_{1} …ω_{n} ∈ Sim(𝔇) by ⟨α⟩ denote a labyrinth ⟨ω_{1}⟩ …⟨ω_{n}⟩. A labyrinth L is snakelike if L ≅ ⟨α⟩ for an α ∈ Sim(𝔇); for a given snakelike labyrinth L the corresponding simple word α is unique and we denote it by α(L).

Proposition 2.1. If (L; x_{0}, x_{1}) is a regular labyrinth, U is an open disk which contains L, then there exists a plane snakelike labyrinth (L_{1}; x_{1}, x_{2}) such that V (L_{1}) ∖ U = \{x_{2}\} and \overline{L} ∩ \overline{L_{1}} = \{x_{1}\}.

Let L = (V, E; x′, x′′) be a labyrinth. If there exists an injective mapping μ: V → R^{2} such that the labyrinth μ(L) = (μ(V), μ(E); μ(x′), μ(x′′)), where μ(E) = {(μ(x), μ(y)) | (x, y) ∈ E} and |(μ(x), μ(y))|_{μ(L)} = |(x, y)|_{L} for every (x, y) ∈ E, is plane, then L is embeddable and μ is an embedding of L. Obviously, if μ is an embedding of L, then L and μ(L) are isomorphic. If, in addition, μ(L) is regular, then L is said to be perfectly embeddable and μ is a perfect embedding of L. In the sequel, by an embedding [a perfect embedding] we sometimes mean μ(L) or even \overline{μ(L)}. For example, if (L; x′, x′′) is a tree, then it is embeddable; moreover, if [x′′]_{L} ≠ 𝔇, then L is perfectly embeddable.

A labyrinth (L; x′, x′′) is called a regular trap for an initial automaton 𝔄 if (L; x′, x′′) is a trap for 𝔄 and if it is perfectly embeddable. A labyrinth (L; x′) is a regular trap for an initial automaton 𝔄 if there exists x′′ ∈ V (L) such that (L; x′, x′′) is a regular trap for 𝔄.

A labyrinth L = (V, E; x′, x′′) is an ω-labyrinth, ω ∈ {e, n}, if [x′] = {ω}, [x′′] = \{\overline{ω}\}, and if there exists an embedding μ of L such that pr_{k_{1}} (μ(x′)) = pr_{k_{1}} (μ(x′′)), pr_{k_{2}} (μ(x′′)) − pr_{k_{2}} (μ(x′)) = r > 0 and

| pr_{k_{2}} (μ(z)) − pr_{k_{2}} (μ(x′))| + | pr_{k_{2}} (μ(x′′)) − pr_{k_{2}} (μ(z))| = r

for every z ∈ V, where (k_{1}, k_{2}) = (2, 1) or (k_{1}, k_{2}) = (1, 2) if ω = e or ω = n respectively; such embedding μ of L is called a standard embedding of ω-labyrinth L. It follows from the definition that for every positive reals r_{1} and r_{2} there exists a standard embedding μ of L such that |\overline{μ(x′)μ(x′ω)} | > r_{1}, |\overline{μ(x′′)μ(x′′\overline{ω})} | > r_{1} and diam(V ∖ {x′, x′′}) < r_{2}.

Let L = (V, E) be a labyrinth and V_{1} ⊆ V. For every x ∈ V, let V_{x} = {x} × (𝔇 ∖ [x]_{L}) and E_{x} = {(x, y) | y ∈ V_{x}} ∪ {(y, x) | y ∈ V_{x}}. By Cross(L, V_{1}) denote the labyrinth (V ∪ (⋃ _{x∈V_{1}} V_{x}), E ∪ (⋃ _{x∈V_{1}} E_{x})) for which |(x, (x, ω))| = ω and |((x, ω), x)| = \overline{ω} for every x ∈ V_{1} and ω ∈ 𝔇 ∖ [x]_{L}, and |(x, y)| = |(x, y)|_{L} for all (x, y) ∈ E. If V_{1} = V, then instead of Cross(L, V) write Cross(L).

Suppose that α = ω_{1} …ω_{n} ∈ Sim(𝔇) and x_{i} = (⟨α⟩; i) for every 0 ⩽ i ⩽ n. Let

⊣α⊢ = Cross(L, {x_{i} | 1 ⩽ i ⩽ n − 1}),  ⊣α⊣ = Cross(L, {x_{i} | 1 ⩽ i ⩽ n}),
⊢α⊢ = Cross(L, {x_{i} | 0 ⩽ i ⩽ n − 1}),  ⊢α⊣ = Cross(L, {x_{i} | 0 ⩽ i ⩽ n}).

Suppose that L is a labyrinth, L_{1} is an e-labyrinth and L_{2} is an n-labyrinth. Arrange in a sequence (x_{1}, y_{1}), …, (x_{m}, y_{m}) all edges (x, y) ∈ E(L) for which |(x, y)| ∈ {e, n}. By Δ(L; L_{1}, L_{2}) denote the labyrinth

(⋯ (L_{x_{1}}+_{y_{1}} L_{κ(x_{1} ,y_{1} )} )_{x_{2}}+_{y_{2}} ⋯_{x_{m−1}} +_{y_{m−1}} L_{κ(x_{m−1} ,y_{m−1} )} )_{x_{m}} +_{y_{m}} L_{κ(x_{m} ,y_{m} )} ,

and by Σ(L; L_{1}, L_{2}) the labyrinth Δ(Cross(L); L_{1}, L_{2}); here, if |(x, y)| = e, then κ(x, y) = 1, and if |(x, y)| = n, then κ(x, y) = 2.

Let L be a labyrinth, L_{1} be an e-labyrinth, L_{2} be an n-labyrinth, and let V_{1} ⊆ V (L). Suppose that L′ is one of the labyrinths Cross(L, V_{1}), Δ(L; L_{1}, L_{2}) and Σ(L; L_{1}, L_{2}). Let us agree that if x ∈ V (L) is the entrance or the exit of L, then x is the entrance or the exit of L′ respectively, unless otherwise stated. It is obvious that the following assertion holds.

Proposition 2.2. Let L_{1} be an e-labyrinth and L_{2} be an n-labyrinth. If L is an embeddable [a perfectly embeddable] labyrinth, then Σ(L; L_{1}, L_{2}) [Δ(L; L_{1}, L_{2})] is an embeddable [a perfectly embeddable] labyrinth, too.

3. The reduction of automata in a plane

Suppose that (L; x′, x′′) is a labyrinth such that [x′]_{L} = {ω} for an ω ∈ 𝔇. If there exists a perfect embedding μ of L such that the ray going out from μ(x′) in the direction \overline{ω} does not intersect with this embedding, then μ is said to be an extraperfect embedding for L, and L is an extraperfectly (or ω-extraperfectly) embeddable labyrinth.

Let 𝔄 = (A, Q, B, φ, ψ) be an automaton, (L; x′, x′′) be an ω-extraperfectly embeddable labyrinth for an ω ∈ 𝔇 and L_{1} = Cross(L, {x′}). If there exists q ∈ Q such that ψ(q, 𝔇) ∈ {ω, 0} and pl(π(𝔄_{q}; L_{1}), {x′, x′′}) ≠ x′′, then 𝔄 is an L-reducible automaton, and L reduces 𝔄. An automaton 𝔄 is reducible if there exists a labyrinth L such that 𝔄 is L-reducible; otherwise it is irreducible. Directly from the definition we get the following proposition.

Proposition 3.1. Let 𝔄 be an irreducible automaton and (L; x′) be a tree such that [x′]_{L} = {ω} for an ω ∈ 𝔇. Then, for every q ∈ Q_{𝔄} and every x ∈ V (L) ∖ {x′} which satisfy that ψ_{𝔄} (q, 𝔇) = ω and [x]_{L} ≠ 𝔇, it holds that tm(π(𝔄_{q}; L_{1}), {x′}) > tm(π(𝔄_{q}; L_{1}), {x}), where L_{1} = Cross(L, {x′}).

Proposition 3.2. If 𝔄 is an irreducible automaton, then |Q_{𝔄}| > 1 and for every q ∈ Q_{𝔄} it holds that ψ_{𝔄} (q, 𝔇) ≠ 0.

Proof. We have that ψ_{𝔄} (q, 𝔇) ≠ 0 for every q ∈ Q_{𝔄} directly from the definition. Now suppose that q_{0} is the unique state of 𝔄. Without loss of generality we can suppose that ψ_{𝔄} (q_{0}, 𝔇) = e. But then the labyrinth ⊣ en ⊢ reduces 𝔄. From the obtained contradiction we get that |Q_{𝔄}| > 1. □

If 𝔄 is L-reducible and L or L^{−1} is an e-labyrinth or an n-labyrinth, then L is an absorbing labyrinth for 𝔄. From Proposition 2.1 we get that the following assertion holds.

Proposition 3.3. If an automaton 𝔄 is reducible, then there exists an absorbing labyrinth for 𝔄.

Assume that 𝔄_{q_{0}} = (A, Q, B, φ, ψ, q_{0}) is an initial automaton such that ω_{1} = ψ(q_{0}, 𝔇) ≠ 0. Take an α = ω_{1} …ω_{n} ∈ Sim(𝔇), n ⩾ 2. Let L = ⊢α⊢ , τ(𝔄_{q_{0}}; L) = x_{0}, x_{1}, … and z_{i} = (⟨α⟩; i) for every 0 ⩽ i ⩽ n. We say that 𝔄_{q_{0}} returns on α if for some i and j, 0 ⩽ i < j < n, there exist m_{1} and m_{2} such that m_{2} < m_{1}, x_{m_{1}} = z_{i}, x_{m_{2}} = z_{j} and x_{k} ≠ z_{n} for every k < m_{1}.

Proposition 3.4. If 𝔄 is an irreducible automaton, then 𝔄_{q} does not return on every ψ_{𝔄}(q, 𝔇)ω_{2} …ω_{n} ∈ Sim(𝔇), n ⩾ 2, for each q ∈ Q_{𝔄}.

Proof. Use the above designations. Suppose, on the contrary, that 𝔄_{q} returns on an α = ω_{1} …ω_{n} ∈ Sim(𝔇), where ω_{1} = ψ_{𝔄} (q, 𝔇) and n ⩾ 2, for a q ∈ Q_{𝔄}. So there exists a trajectory segment x_{m_{3}} , …, x_{m_{2}} , …, x_{m_{1}} , m_{3} < m_{2} < m_{1}, such that for some i and j, 0 ⩽ i < j < n, it holds that x_{m_{1}} = x_{m_{3}} = z_{i} and x_{m_{2}} = z_{j}. Hence ⊣ω_{i+1} …ω_{n} ⊢ reduces 𝔄. Contradiction. □

Suppose that 𝔄 = (A, Q, B, φ, ψ) is an automaton, L_{1} is an e-labyrinth and L_{2} is an n-labyrinth. Let K = Δ(L(𝔇); L_{1}, L_{2}) and π(q) = π(𝔄_{q}; K) for every q ∈ Q. Suppose that for some q ∈ Q the value q′ = st(π(q), V (𝔇)) exists. Then, if pl(π(q), V (𝔇)) = x_{0}, write q ≃^{∗} q′, and if pl(π(q), V (𝔇)) = x_{ω}, ω ∈ 𝔇, write q ⇒^{∗} q′. By ≃ denote the smallest equivalence relation on Q that contains ≃^{∗} , and by ⇒ the composition of relations ≃ and ⇒^{∗} .

Let Q(L_{1}, L_{2}) = {q ∈ Q | (∃q′) q ⇒ q′} and q_{0} ∈ Q. For every q ∈ Q, if q ∈ Q(L_{1}, L_{2}) and q ≄ q_{0}, let [q] = {q′ ∈ Q | q′ ≃ q}; otherwise [q] = (Q ∖ Q(L_{1}, L_{2})) ∪ {q′ ∈ Q | q′ ≃ q_{0}}. Let Q′ = {[q] | q ∈ Q} (generally, Q′ ≠ Q/≃ ). Construct the automaton 𝔄[L_{1}, L_{2}, q_{0}] = (A, Q′, B, φ′, ψ′) in the following way. Given an arbitrary a ∈ P_{0}(𝔇). For every q ∈ Q(L_{1}, L_{2}), if the value q′ = st(π(q), V′(a)) exists, let φ′([q], a) = [q′] and ψ′([q], a) = ω(q), where ω(q) such that x_{ω(q)} = pl(π(q), V′(a)), and if st(π(q), V′(a)) is not defined, let φ′([q], a) = [q] and ψ′([q], a) = 0; additionally, if q_{0} ∈ Q ∖ Q(L_{1}, L_{2}), take that φ′([q], a) = [q] and ψ′([q], a) = 0 for every q ∈ Q ∖ Q(L_{1}, L_{2}). Finally, by taking that φ′([q], ∅) = [q] and ψ′([q], ∅) = 0 for every q ∈ Q, we have completely defined the functions φ′ and ψ′ (for every element of Q′× A). For every q ∈ Q, by 𝔄[L_{1}, L_{2}, q_{0}; q] denote the automaton 𝔄[L_{1}, L_{2}, q_{0}] with the initial state [q]. Note that |Q_{𝔄[L_{1} ,L_{2} ,q_{0} ]} | ⩽ |Q_{𝔄}| for every q_{0} ∈ Q_{𝔄}.

Obviously the following assertion holds.

Proposition 3.5. Let L_{1} be an e-labyrinth, L_{2} be an n-labyrinth, and let 𝔄 be an automaton such that |Q_{𝔄}| > 1. If one of the labyrinths L_{1}, L_{2}, L_{1}^{−1} and L_{2}^{−1} is an absorbing labyrinth for 𝔄, then there exists q_{0} ∈ Q_{𝔄} such that |Q_{𝔄[L_{1} ,L_{2} ,q_{0} ]} | < |Q_{𝔄}|.

Further on, when we consider the automaton 𝔄[L_{1}, L_{2}, q_{0}] and if the conditions of the previous proposition are satisfied, then q_{0} is chosen in such a way that |Q_{𝔄[L_{1} ,L_{2} ,q_{0} ]} | < |Q_{𝔄}|. If it is not important which q_{0} satisfying the condition of the last proposition we have chosen, or if it is clear from the context which q_{0} is meant, then instead of 𝔄[L_{1}, L_{2}, q_{0}] we write simply 𝔄[L_{1}, L_{2}].

The first of the following two assertions follows from Propositions 3.2 and 3.3, and the second one is obvious.

Proposition 3.6. If 𝔄 is an automaton satisfying |Q_{𝔄}| = 1, then there exist an e-labyrinth L_{1} and an n-labyrinth L_{2} such that the automaton 𝔄[L_{1}, L_{2}] is trivial.

Proposition 3.7. If 𝔄 is a trivial automaton, then 𝔄[L_{1}, L_{2}] is trivial for every e-labyrinth L_{1} and n-labyrinth L_{2}.

Suppose that 𝔄 is an initial automaton, (L; y_{0}) is a labyrinth and W ⊆ V (L). Let x_{0}, x_{1}, … be the W -trajectory of 𝔄 in (L; y_{0}). The sequence (finite or infinite) which we obtain by replacing each maximal block of equal elements in x_{0}, x_{1}, … with one of these elements (i.e., every finite segment x, y, …, y, z and, if it exists, the infinite segment x, y, y, … in x_{0}, x_{1}, … is replaced with x, y, z and x, y respectively; here, x ≠ y and y ≠ z) is called the cleaned W -trajectory of 𝔄 in (L; y_{0}).

Given two automata 𝔄_{1} and 𝔄_{2}, two labyrinths L_{1} and L_{2}, and a mapping f: Q_{𝔄_{2}} → Q_{𝔄_{1}}. We say that the pair (𝔄_{1}, L_{1}) f-imitates the pair (𝔄_{2}, L_{2}), and we write (𝔄_{1}, L_{1}) ⩽_{f} (𝔄_{2}, L_{2}), if:

(1) there exist a V′ ⊆ V (L_{2}) and a bijection g: V (L_{1}) → V′ such that for every x_{0} ∈ V (L_{1}) and for every q ∈ Q_{𝔄_{2}} the cleaned V′-trajectory of (𝔄_{2})_{q} in (L_{2}; g(x_{0})) is either the infinite sequence g(x_{0}), g(x_{1}), … or the

finite sequence g(x_{0}), g(x_{1}), …, g(x_{m}) for some m ⩾ 0, where
τ((𝔄_{1})_{f(q)} ; (L_{1}; x_{0})) = x_{0}, x_{1}, …;

(2) for an x_{0} ∈ V (L_{1}) and a q ∈ Q_{𝔄_{2}}, (L_{1}; x_{0}) is a regular trap for (𝔄_{1})_{f(q)} ,

then (L_{2}; g(x_{0})) is a regular trap for (𝔄_{2})_{q}.

We say that 𝔄_{1} imitates 𝔄_{2}, and we write 𝔄_{1} ⩽ 𝔄_{2}, if there exists a mapping f: Q_{𝔄_{2}} → Q_{𝔄_{1}} such that for every labyrinth L_{1} there exists a labyrinth L_{2} satisfying that (𝔄_{1}, L_{1}) ⩽_{f} (𝔄_{2}, L_{2}). The following theorem holds.

Theorem 3.1. If 𝔄 is an automaton, L_{1} is an e-labyrinth and L_{2} is an nlabyrinth, then 𝔄[L_{1}, L_{2}] ⩽ 𝔄.

Proof. Use the above given designations. Let f(q) = [q] for every q ∈ Q_{𝔄}. Given an arbitrary labyrinth L. Consider the labyrinth L′ = Σ(L; L_{1}, L_{2}). Take g: V (L) → V (L′) such that g(x) = x for every x ∈ V (L). Directly from the definition of the automaton 𝔄[L_{1}, L_{2}] we get: 1) the first condition of the above definition holds for the pairs (𝔄[L_{1}, L_{2}], L) and (𝔄, L′); and 2) if (L; x_{0}, y_{0}) is a regular trap for (𝔄[L_{1}, L_{2}])_{f(q)} , then for some ω ∈ 𝔇 ∖ [y_{0}]_{L}, the labyrinth (L′; g(x_{0}), (y_{0}, w)) is a regular trap for 𝔄_{q} (see Proposition 2.2). Therefore, (𝔄[L_{1}, L_{2}], L) ⩽_{f} (𝔄, L′), and as L is an arbitrary labyrinth, we have that 𝔄[L_{1}, L_{2}] ⩽ 𝔄. □

Theorem 3.2. The relation ⩽ in the set of all automata is transitive.

Proof. Let 𝔄_{1}, 𝔄_{2} and 𝔄_{3} be automata. Suppose that 𝔄_{1} ⩽ 𝔄_{2} and 𝔄_{2} ⩽ 𝔄_{3}. From 𝔄_{1} ⩽ 𝔄_{2} [𝔄_{2} ⩽ 𝔄_{3}] it follows that there exists a mapping f_{1} : Q_{𝔄_{2}} → Q_{𝔄_{1}} [f_{2} : Q_{𝔄_{3}} → Q_{𝔄_{2}}] such that for every labyrinth K_{1} [M_{1}] there exists a labyrinth K_{2} [M_{2}] satisfying (𝔄_{1}, K_{1}) ⩽_{f_{1}} (𝔄_{2}, K_{2}) [(𝔄_{2}, M_{1}) ⩽_{f_{2}} (𝔄_{3}, M_{2})]. Let f_{3} = f_{1} ∘ f_{2}. Take an arbitrary labyrinth L_{1}. As we have seen, there exists a labyrinth L_{2} such that (𝔄_{1}, L_{1}) ⩽_{f_{1}} (𝔄_{2}, L_{2}), and there exists a labyrinth L_{3} such that (𝔄_{2}, L_{2}) ⩽_{f_{2}} (𝔄_{3}, L_{3}). Showing that (𝔄_{1}, L_{1}) ⩽_{f_{3}} (𝔄_{3}, L_{3}), we get that 𝔄_{1} ⩽ 𝔄_{3}, which proves the theorem.

So, there exist a W_{1} ⊆ V (L_{2}) and a bijection g_{1} : V (L_{1}) → W_{1} such that for every (q, x_{0}) ∈ Q_{𝔄_{2}} ×V (L_{1}) the cleaned W_{1}-trajectory of (𝔄_{2})_{q} in (L_{2}; g_{1}(x_{0})) is either g_{1}(x_{0}), g_{1}(x_{1}), … or g_{1}(x_{0}), …, g_{1}(x_{m}) for an m ⩾ 0, where τ((𝔄_{1})_{f_{1} (q)} ; (L_{1}; x_{0})) = x_{0}, x_{1}, … Also, there exist a W_{2} ⊆ V (L_{3}) and a bijection g_{2} : V (L_{2}) → W_{2} such that for every (q′, y_{0}) ∈ Q_{𝔄_{3}} × V (L_{2}) the cleaned W_{2}-trajectory of (𝔄_{3})_{q′} in (L_{3}; g_{2}(y_{0})) is either g_{2}(y_{0}), g_{2}(y_{1}), … or g_{2}(y_{0}), …, g_{2}(y_{n}) for an n ⩾ 0, where τ((𝔄_{2})_{f_{2} (q′)} ; (L_{2}; y_{0})) = y_{0}, y_{1}, …

By g_{3} denote the bijection g_{2} ∘ g_{1} : V (L_{1}) → W_{3}, where W_{3} = g_{2}(W_{1}) ⊆ V (L_{3}). Take an x̂_{0} ∈ V (L_{1}) and a q̂ ∈ Q_{𝔄_{3}}. Let τ((𝔄_{2})_{f_{2} (q̂)} ; (L_{2}; g_{1}(x̂_{0}))) = ŷ_{0}, ŷ_{1}, … and τ((𝔄_{1})_{f_{3} (q̂)} ; (L_{1}; x̂_{0})) = x̂_{0}, x̂_{1}, … But from our assumption it follows that there exists a finite or an infinite sequence of integers 0 = i_{0} < i_{1} < i_{2} < … such that ŷ_{i_{j}} = g_{1}(x̂_{j} ) for every element i_{j} of this sequence, and ŷ_{i_{0}} , ŷ_{i_{1}} , … is the cleaned W_{1}-trajectory of (𝔄_{2})_{f_{2} (q̂)} in (L_{2}; g_{1}(x̂_{0})). As W_{3} ⊆ W_{2}, and as the cleaned W_{2}-trajectory of (𝔄_{3})q̂ in (L_{3}; g_{2}(g_{1}(x̂_{0}))) is either g_{2}(ŷ_{0}), g_{2}(ŷ_{1}), … or g_{2}(ŷ_{0}), …, g_{2}(ŷn̂) for some n̂ ⩾ 0, then the cleaned W_{3}-trajectory of (𝔄_{3})q̂ in (L_{3}; g_{3}(x̂_{0})) is either g_{2}(ŷ_{i_{0}} ), g_{2}(ŷ_{i_{1}} ), … or g_{2}(ŷ_{i_{0}} ), …, g_{2}(ŷ_{im̂} ), i.e., is either g_{3}(x̂_{0}), g_{3}(x̂_{1}), … or g_{3}(x̂_{0}), …, g_{3}(x̂m̂), for some m̂ ⩾ 0.

Further, if for an x_{0} ∈ V (L_{1}) and a q ∈ Q_{𝔄_{3}}, (L_{1}; x_{0}) is a regular trap for (𝔄_{1})_{f_{1} ∘f_{2} (q)} , then (L_{2}; g_{1}(x_{0})) is a regular trap for (𝔄_{2})_{f_{2} (q)} , and, consequently, (L_{3}; g_{2} ∘ g_{1}(x_{0})) is a regular trap for (𝔄_{3})_{q}. So we have that (𝔄_{1}, L_{1}) ⩽_{f_{3}} (𝔄_{3}, L_{3}), and our assertion is true. □

Theorem 3.3. Let 𝔄_{1}, …, 𝔄_{n} be arbitrary automata. Then there exist automata 𝔄′_{1}, …, 𝔄′_{n}, satisfying that each of them is irreducible or trivial, such that 𝔄′_{i} ⩽ 𝔄_{i} for every 1 ⩽ i ⩽ n.

Proof. Take an arbitrary e-labyrinth L_{1} and an arbitrary n-labyrinth L_{2}. Let 𝔄_{i}^{(0)} = 𝔄_{i}[L_{1}, L_{2}] for every 1 ⩽ i ⩽ n. If for some 1 ⩽ j ⩽ n, either |Q_{𝔄_{j}^{(0)}} | > 1

and 𝔄_{j}^{(0)} is reducible or |Q_{𝔄_{j}^{(0)}} | = 1 and 𝔄_{j}^{(0)} is non-trivial, then Propositions

3.5 and 3.6 imply that there exist an e-labyrinth L_{1}^{(0)} and n-labyrinth L_{2}^{(0)} such that |Q_{𝔄_{j}^{(0)} [L_{1}^{(0)} , L_{2}^{(0)} ]} | < |Q_{𝔄_{j}^{(0)}} | or 𝔄_{j}^{(0)}[L_{1}^{(0)}, L_{2}^{(0)}] is trivial respectively. Let 𝔄_{i}^{(1)} =

𝔄_{i}^{(0)}[L_{1}^{(0)}, L_{2}^{(0)}] for every 1 ⩽ i ⩽ n. Continue with this procedure and suppose that we obtain automata 𝔄_{i}^{(k)}, 1 ⩽ i ⩽ n. If for a 1 ⩽ j ⩽ n, either |Q_{𝔄_{j}^{(k)}} | > 1 and 𝔄_{j}^{(k)} is reducible or |Q_{𝔄_{j}^{(k)}} | = 1 and 𝔄_{j}^{(k)} is non-trivial, then there exist an e-labyrinth

L_{1}^{(k)} and n-labyrinth L_{2}^{(k)} such that

(3.1)  |Q_{𝔄_{j}^{(k)} [L_{1}^{(k)} , L_{2}^{(k)} ]} | < |Q_{𝔄_{j}^{(k)}} |

or 𝔄_{j}^{(k)}[L_{1}^{(0)}, L_{2}^{(k)}] is trivial respectively. Let 𝔄_{i}^{(k+1)} = 𝔄_{i}^{(k)}[L_{1}^{(k)}, L_{2}^{(k)}] for every 1 ⩽ i ⩽ n. Because of (3.1) and Proposition 3.7 this procedure must be finished, i.e., there exists a minimal integer m ⩾ 0 such that 𝔄_{i}^{(m)} is trivial or irreducible for every 1 ⩽ i ⩽ n. Let 𝔄′_{i} = 𝔄_{i}^{(m)} for every 1 ⩽ i ⩽ n. Fix an 1 ⩽ i ⩽ n. From Theorem 3.1 it follows immediately that 𝔄_{i}^{(k+1)} = 𝔄_{i}^{(k)}[L_{1}^{(k)}, L_{2}^{(k)}] ⩽ 𝔄_{i}^{(k)}. Hence, we have that 𝔄′_{i} = 𝔄_{i}^{(m)} ⩽ ⋯⩽ 𝔄_{i}^{(1)} ⩽ 𝔄_{i}^{(0)} ⩽ 𝔄_{i}, and from Theorem 3.2, we get that 𝔄′_{i} ⩽ 𝔄_{i}. □

Let 𝔄_{q_{0}} = (A, Q, B, φ, ψ, q_{0}) be an initial automaton, σ be one of the two permutations

σ_{r} = ( \begin{matrix}e & n & w & s \\ n & w & s & e \end{matrix}) and σ_{l} = ( \begin{matrix}e & s & w & n \\ s & w & n & e \end{matrix})

of the set 𝔇 and ω_{0} ∈ 𝔇. Let us introduce two special classes of labyrinths which play an important role in the sequel.

Suppose that L_{0} = L_{2} = ⟨ω_{0}⟩, L_{1} is a σ(ω_{0})ω_{0}-tree, and y_{0} ∈ V (L_{1}). Let L′ = Cross(L_{0}L_{1}L_{2}, {x_{0}, x_{1}, x_{2}, x_{3}}), where x_{i} = (L_{0}L_{1}L_{2}; i) for every 0 ⩽ i ⩽ 3, and π = π(𝔄_{q_{0}}; L′). The 4-tuple (L_{0}, L_{1}, L_{2}; y_{0}) is a pre-absorbing (or (ω_{0}, σ)-pre-absorbing) labyrinth for 𝔄_{q_{0}} if:

(1) for every δ > 0 and Δ > 0 there exists a extraperfect embedding μ of (L_{0}L_{1}L_{2} _{x_{1}}+_{x_{3}} ⟨ω_{0}⟩⟨σ(ω_{0})⟩; x_{0}, y_{0}) such that |\overline{μ(x_{1})μ(x_{1}σ(ω_{0}))} | > Δ, |\overline{μ(x_{2})μ(x_{2} \overline{ω_{0}} )} | > Δ and diam μ(V (L_{0}L_{1}L_{2}) ∖ \{x_{0}, x_{1}, x_{2}, x_{3}\}) < δ;

(2) ψ(q_{0}, 𝔇) = ω_{0}, ω_{1} = dr_{0}(π, {x_{3}}) ∈ {σ(ω_{0}), ω_{0}}, dr_{0}(π, {x_{1}}) = σ(ω_{0})

and pl(π, {x_{3}, y_{0}}) = x_{3}

(in Fig. 1a is given an (e, σ_{r})-pre-absorbing labyrinth).

Note that the figures given in the paper represent plane labyrinths or the embeddings of labyrinths by their realizations. A point v of such a realization W is a vertex of the given plane labyrinth or of the given embedding iff there does not exist an open disk with the center at v whose intersection with W is an open segment or v is marked with a small black closed disk.

Assume that L′_{1} = ⟨ω_{0}⟩, L′′_{1} is a ω_{1}σ(ω_{0})-tree, where ω_{1} ≠ \overline{ω_{0}} , and L_{2} = ⟨σ(ω_{0})⟩. Let L_{1} = Cross(L′_{1}L′′_{1}, {z_{1}}) and y_{0} ∈ V (L_{1}), where z_{i} = (L′_{1}L′′_{1}; i) for each 0 ⩽ i ⩽ 2. Also, let x_{j} = (L_{1}L_{2}; j) for each 0 ⩽ j ⩽ 2. The ordered 3-tuple (L_{1}, L_{2}; y_{0}) is an (ω_{0}, σ)-incomplete pre-absorbing labyrinth for 𝔄_{q_{0}} if:

(1) for every δ, Δ ∈ R^{+} there exists a perfect embedding μ of the labyrinth (L_{1}L_{2} _{x_{0}}+_{x_{2}} ⟨σ(ω_{0})⟩⟨ω_{0}⟩; x_{0}, y_{0}) satisfying

|\overline{μ(x_{0})μ(x_{0}ω_{0})} | > Δ, |\overline{μ(x_{1})μ(x_{2})} | > Δ, diamμ(V (L_{1}L_{2}) ∖ \{x_{0}, x_{2}\}) < δ;

(2) ψ(q_{0}, 𝔇) = ω_{0} and pl(π(𝔄_{q_{0}}; Cross(L_{1}L_{2}, {x_{0}, x_{1}, x_{2}})), {x_{2}, y_{0}}) = x_{2}.

Because of condition (1) from the above definition, an (ω_{0}, σ)-incomplete preabsorbing labyrinth (L_{1}, L_{2}; y_{0}), given in Fig. 1b, will be depicted as in Fig. 1c (here, ω_{0} = e, ω_{1} = n, and σ = σ_{l}).

Figure 1.

Theorem 3.4. Let 𝔄 be an automaton. If for a q_{0} ∈ Q_{𝔄} there exists a preabsorbing labyrinth (L_{0}, L_{1}, L_{2}; z_{0}) for 𝔄_{q_{0}}, then 𝔄 is reducible.

Proof. We use the above given designations. Obviously m = |Q_{𝔄}| > 1. Let L_{4} = (V_{4}, E_{4}; x′_{4}, x′′_{4}) = ⟨\overline{ω_{0}} ⟩^{m_{1}} , L_{5} = (V_{5}, E_{5}; x′_{5}, x′′_{5}) = ⟨\overline{ω_{0}} ⟩^{m_{2}} , V′_{4} = V_{4} ∖ \{x′_{4}, x′′_{4}\} and V′_{5} = V_{5} ∖ {x′_{5}, x′′_{5}}; here m_{1} and m_{2} are natural numbers which we are going to determine. Obviously there exists an ω_{1}σ^{−1} (ω_{0})-tree L_{3} such that for every m_{1} and m_{2} the labyrinth

L = ((L_{0} …L_{5} _{x_{5}} +_{x_{3}} ⟨σ(ω_{0})⟩) _{x_{6}} +_{x_{1}} ⟨\overline{ω_{0}} ⟩; x_{0}, z_{0}),

where x_{i} = (L_{0} …L_{5}; i) for every 0 ⩽ i ⩽ 6, is extraperfectly embeddable. Suppose that ω_{0} = ω_{1} = w and σ = σ_{l} (see Fig. 2); the other cases are discussed similarly. Take some m_{1} ⩾ m + 1, and put L′ = Cross(L, {x_{i} | 0 ⩽ i ⩽ 6} ∪ V′_{4} ∪ V′_{5}). Let π = π(𝔄_{q_{0}}; L′) and π_{t} = π_{t}(𝔄_{q_{0}}; L′) for every t ⩾ 0. Prove the theorem by contradiction, that is, suppose that 𝔄 is irreducible.

Figure 2.

Since dr_{0}(π, {x_{1}}) = n and dr_{0}(π, {x_{3}}) = w, then from Proposition 3.1 it follows that 𝔄_{q_{0}} cannot find itself again in x_{1} and x_{3} until it searches all the vertices of the set V′_{4} ∪ {x_{5}}. Note that if 𝔄_{q_{0}} finds itself in some vertex z ∈ V′_{4}∪ V′_{5}∪ {x_{1}, x_{5}, x_{6}} at some moment t > 1 and |(pr_{2}(π_{t−1} ), pr_{2}(π_{t}))| = e, then \overline{dr}_{0}(π, t) = (sn)^{k_{0}} n … (case 1 for z) or \overline{dr}_{0}(π, t) = (sn)^{k_{0}} e … (case 2 for z) for some k_{0} ⩾ 0 (since 𝔄 is irreducible, \overline{dr}_{0}(π, t) ≠ (sn)^{k_{0}} w …; otherwise ⊣ e^{2} ⊢ reduces 𝔄).

Let y_{i} = x_{4}(\overline{ω_{0}} )^{i} for every 1 ⩽ i ⩽ m_{1} + m_{2}; note that y_{m_{1}} = x_{5} and y_{m_{1} +m_{2}} = x_{6}. If 𝔄_{q_{0}} finds itself for the first time in x_{5}, and for x_{5} case 2 holds, then, since m_{1} ⩾ m + 1, there exists 1 ⩽ m_{0} ⩽ m such that case 2 holds for all the vertices y_{m_{1} +jm_{0}} , where jm_{0} < m_{2} and j ∈ N. Now if we choose m_{2} = 2m_{0} − 1, then for x_{1} case 2 takes place, and, consequently, 𝔄 is (L′; x_{0}, z_{0})-reducible. Hence case 1 holds for x_{5}, and 𝔄_{q_{0}} finds itself at a moment t′ > t again in x_{3} (assume that t′ is the first of such moments). Now if \overline{dr}_{0}(π, t′) = (ns)^{k_{0}} e … for a k_{0} ⩾ 0, then the labyrinth

L̃ = Cross(L_{2} …L_{5} _{x′_{3}} +_{x′_{1}} ⟨σ(ω_{0})⟩, {x′_{1}, x′_{2}, x′_{3}} ∪ V′_{4})

reduces 𝔄, where x′_{i} = (L_{2} …L_{5}; i), 0 ⩽ i ⩽ 4, and m_{2} = 1; if \overline{dr}_{0}(π, t′) = (ns)^{k_{1}} s … for a k_{1} ⩾ 0, then ⊣ nw ⊢ reduces 𝔄. Therefore, we may suppose that \overline{dr}_{0}(π, t′) = (ns)^{k_{2}} w … for a k_{2} ⩾ 0. Hence 𝔄_{q_{0}} reaches x_{5} again without visiting vertex x_{3}, and we may repeat our reasoning. But if 𝔄_{q_{0}} visits x_{5} more than m times and case 1 always takes place for x_{5}, then 𝔄_{q_{0}} “moves in loops”, and L̃ again reduces 𝔄. Contradiction. □

Suppose that 𝔄 is an initial automaton, (L; x_{0}) is a labyrinth and τ = y_{0}, y_{1}, … is the cleaned trajectory of 𝔄 in (L; x_{0}) (τ is finite or infinite). Let z ∈ V (L)∖Lf(L), where Lf(L) is the set of all leaves of L. A finite segment τ′ = y_{m}, y_{m+1} , …, y_{n} (0 ⩽ m ⩽ n) or an infinite segment τ′ = y_{m}, y_{m+1} , … (m ⩾ 0) of τ is called a z-block of τ if τ′ has at least one appearance of z and contains, besides z, only leaves of L. A z-block τ′ of τ is regular if it is maximal, i.e., there is no other different z-block which contains τ′. A segment τ′ of τ is a regular block if there exists a z ∈ V (L) such that τ′ is a regular z-block.

If τ contains at least one z ∉ Lf(L), then it has at least one regular block, its regular blocks cover it, and any two different regular blocks of τ are disjoint.

Suppose that τ′ is a regular block of τ. Let z ∈ V (L) ∖ Lf(L) be such that τ′ is a regular z-block. Perform the following procedure on the elements of τ′ beginning with the first and taking them one by one: if a segment of the form z, w, z, where w ∈ Lf(L), appears in τ′ for the first time, do not touch it, and if we have already had a segment exactly the same, then replace it by z (e.g., this procedure transforms z-block z, w_{1}, z, w_{2}, z, w_{2}, z, w_{1}, z, w_{3}, z, where w_{1}, w_{2} and w_{3} are different leaves of L, into z, w_{1}, z, w_{2}, z, w_{3}, z). Perform the above procedure on each regular block of τ. The obtained sequence is called the doubly cleaned trajectory of 𝔄 in (L; x_{0}).

An initial automaton 𝔄_{q_{0}} is a snakelike σ_{0}-walker, σ_{0} ∈ {σ_{r}, σ_{l}}, if ω_{1} = ψ_{𝔄_{q_{0}}} (q_{0}, 𝔇) ≠ 0, and if for every α = ω_{1} …ω_{n} ∈ Sim(𝔇), n ⩾ 2, the doubly cleaned trajectory y_{0}, y_{1}, … of 𝔄_{q_{0}} in ⊢ α ⊢ is such that there exists i_{0} = min{j | y_{j} = x_{f}(⊢ α ⊢)}, and it holds that |(y_{i}, y_{i+1} )| = σ_{0}(|(y_{i}, y_{i−1} )|) for every 1 ⩽ i ⩽ i_{0} − 1 satisfying that y_{i} is not a leaf. A snakelike σ_{0}-walker is a snakelike rightwalker [snakelike leftwalker] if σ_{0} = σ_{r} [σ_{0} = σ_{l}].

Theorem 3.5. If 𝔄 is an irreducible automaton, and if for a q_{0} ∈ Q_{𝔄} and a σ_{0} ∈ {σ_{r}, σ_{l}} the initial automaton 𝔄_{q_{0}} is not a snakelike σ_{0}-walker, then there exists a (ψ_{𝔄}(q_{0}, 𝔇), σ_{0})-incomplete pre-absorbing labyrinth for 𝔄_{q_{0}}.

Proof. Note that Proposition 3.2 implies that ω_{1} = ψ_{𝔄}(q_{0}, 𝔇) ≠ 0. As Propositions 3.1 and 3.4 hold, and as 𝔄_{q_{0}} is not a snakelike σ_{0}-walker, then there exist the shortest word α = ω_{1} …ω_{m} ∈ Sim(𝔇), m ⩾ 2, such that y_{k+1} = x_{f}(⊢ α ⊢), |(y_{k}, y_{k+1} )| = ω_{m}, σ_{0}(|(y_{k}, y_{k−1} )|) ≠ ω_{m}, and y_{j} ≠ x_{f}(⊢ α ⊢) for some k ⩾ 1 and for each 0 < j < k, where y_{0}, y_{1}, … is the doubly cleaned trajectory of 𝔄_{q_{0}} in ⊢ α ⊢. Let α_{1} = ασ_{0}(ω_{m})\overline{α}σ_{0}(ω_{1}), L_{1} = ⊣ α_{1} ⊢, L_{2} = ⟨σ_{0}(ω_{1})⟩, and

z_{0} = (x_{s}(L_{1})ω_{1} …ω_{m−1} σ_{0}(|(y_{k}, y_{k−1} )|))_{L_{1}} .

Clearly, (L_{1}, L_{2}; z_{0}) is an (ω_{1}, σ_{0})-incomplete absorbing labyrinth for 𝔄_{q_{0}}. □

In the sequel, wherever we use the result of the last assertion, by ∗α| denote the word ασ_{0}(ω_{m})\overline{α}σ_{0}(ω_{1}), by |α∗ denote σ_{0}(ω_{1}), and let ∗α∗ = ∗α||α∗. Denote the (ω_{1}, σ_{0})-incomplete pre-absorbing labyrinth (L_{1}, L_{2}; z_{0}) constructed in the proof of Theorem 3.5 by (L_{1}, L_{2}; z_{0}; α).

By L_{plwl} denote the class of all plane labyrinths without leaves. An initial automaton 𝔄_{q_{0}} is a σ_{0}-walker, σ_{0} ∈ {σ_{r}, σ_{l}}, if for every L ∈ L_{plwl} and every x_{0} ∈ V (L) the doubly cleaned V (L)-trajectory y_{0}, y_{1}, … of 𝔄_{q_{0}} in (Cross(L); x_{0}) is infinite and |(y_{i}, y_{i+1} )| = σ_{0}(|(y_{i}, y_{i−1} )|) for every i ⩾ 1 satisfying that y_{i} ∈ V (L); we say that a σ_{0}-walker 𝔄_{q_{0}} is a σ_{0}-walker with the guided vector ω if |(y_{0}, y_{1})| = |(x_{0}, y_{1})| is always the first element from [y_{0}]_{L} which goes after \overline{ω} according to σ_{0}. A σ_{0}-walker 𝔄_{q_{0}} is said to be a rightwalker [leftwalker] if σ_{0} = σ_{r} [σ_{0} = σ_{l}].

Proposition 3.8. Let 𝔄 be an irreducible automaton, q_{0} ∈ Q_{𝔄}, and α = ω_{1} …ω_{n} ∈ Sim(𝔇), where ω_{1} = ψ_{𝔄} (q_{0}, 𝔇) and n ⩾ 2. If 𝔄_{q_{0}} is a snakelike σ_{0}- walker, σ_{0} ∈ {σ_{r}, σ_{l}}, then 𝔄_{q_{1}}, where q_{1} = st(π(𝔄_{q_{0}}; ⊢ α ⊢), {x_{f}(⊢ α ⊢)}), is a σ_{0}-walker with the guided vector ω_{n}.

Assume that 𝔄 = (A, Q, B, φ, ψ) is an automaton and ω ∈ 𝔇. A q ∈ Q is called an ω-turning state of 𝔄 if for some σ_{0} ∈ {σ_{l}, σ_{r}} it holds that ψ(q, 𝔇) = ω and ψ(φ(q, 𝔇), 𝔇) = σ_{0}(\overline{ω}). A state q of 𝔄 is a turning state of 𝔄 if there exists ω ∈ 𝔇 such that q is an ω-turning state of 𝔄.

Let q_{0} be a state of an automaton 𝔄 such that ω_{1} = ψ_{𝔄} (q_{0}, 𝔇) ≠ 0, and let α = ω_{1} …ω_{n} ∈ Sim(𝔇), n ⩾ 1. Suppose that π = π(𝔄_{q_{0}}; ⊢ α ⊢ ) = (q_{0}, x_{0}), (q_{1}, x_{1}), … and z_{j} = (⟨α⟩; j) for each 0 ⩽ j ⩽ n. We say that q_{0} can be turned by α if there exists t_{1} ⩾ 0 such that x_{t_{1}} = z_{n−1} , q_{t_{1}} = trn(q_{0}, α) is a ω_{n}-turning state of 𝔄, and x_{t} ≠ z_{n} for every 0 ⩽ t ⩽ t_{1}. A state q of 𝔄 can be turned if there exists α ∈ Sim(𝔇) such that q can be turned by α.

Theorem 3.6. Each state of an irreducible automaton 𝔄 = (A, Q, B, φ, ψ) can be turned.

Proof. Suppose our assertion does not hold for a q ∈ Q. Without loss of generality take that ψ(q, 𝔇) = w. Consider the labyrinth (L; y_{0}) given in Fig. 3. Let L′ = Cross((L; y_{0}), {y_{0}}), τ(𝔄_{q}; L′) = x_{0}, x_{1}, … and π = π(𝔄_{q}; L′). Proposition

Figure 3.

3.2 implies that there is no i ⩾ 0 such that x_{i} = x_{i+1} = y_{j} for an 1 ⩽ j ⩽ 5. Now from our assumption we get that x_{0} = y_{0}, x_{1} = y_{1} and x_{2} = y_{2}. Notice that from the irreducibility of 𝔄 it follows that pl(π, {y_{0}, z_{0}}) ≠ y_{0}. According to Proposition 3.4, 𝔄_{q} does not return on any of the words w^{2}s(senws )^{k}, k ⩾ 0. As Proposition 3.1 holds and q cannot be turned by any of the words w^{2}s(senws )^{k}, 0 ⩽ k ⩽ |Q|, then the labyrinth (L; y_{0}, z_{0}) reduces 𝔄_{q}. Contradiction. □

Let 𝔄 be an automaton. A state q ∈ Q_{𝔄} orients 𝔄 [with the guided vector ω] if 𝔄_{q} is an leftwalker or an rightwalker [with the guided vector ω].

Assume that 𝔄_{q_{0}} is an initial automaton, L_{1} is a snakelike e-labyrinth and L_{2} is a snakelike n-labyrinth. Let L = Δ(L(𝔇); ⊣ α(L_{1}) ⊢, ⊣ α(L_{2}) ⊢). We say that the pair (L_{1}, L_{2}) orients 𝔄_{q_{0}} if the state st(π(𝔄_{q_{0}}; L), V′(𝔇)) exists and orients 𝔄 with the guided vector ω, where x_{ω} = pl(π(𝔄_{q_{0}}; L), V′(𝔇)); denote the state st(π(𝔄_{q_{0}}; L), V′(𝔇)) by q(𝔄_{q_{0}}; L_{1}, L_{2}).

Theorem 3.7. If an automaton 𝔄 = (A, Q, B, φ, ψ) is irreducible, then for every q ∈ Q_{𝔄} there exist a snakelike e-labyrinth L_{1} and a snakelike n-labyrinth L_{2} such that the pair (L_{1}, L_{2}) orients 𝔄_{q}.

Proof. Fix a q_{0} ∈ Q_{𝔄}. Introduce four variables β_{e}, β_{w}, β_{n} and β_{s} whose values are words from the set Sim(𝔇) ∪ {Λ} and take Λ as their initial value, i.e., take that β_{e} := Λ, β_{w} := Λ, β_{n} := Λ, and β_{s} := Λ.

As 𝔄 is irreducible, then ω = φ(q_{0}, 𝔇) ≠ 0 for an ω ∈ 𝔇, and from Theorem 3.6 it follows that there exists a word α_{0} ∈ Sim(𝔇) such that q_{0} can be turned by α_{0}. Let q_{1} = trn(q_{0}, α_{0}) be an ω_{0}-turning state and ψ(q_{2}, 𝔇) = ω_{1} = σ_{0}(\overline{ω_{0}} ), where q_{2} = φ(q_{1}, 𝔇) and σ_{0} ∈ {σ_{l}, σ_{r}} (in Fig. 4 we suppose that ω_{0} = w, ω_{1} = s and σ_{0} = σ_{l}).

If 𝔄_{q_{2}} is a snakelike σ_{0}-walker, then put β_{ω} := α_{0}ω_{1}. If 𝔄_{q_{2}} is not a snakelike σ_{0}-walker, then from Theorem 3.5 it follows that there exists an (ω_{1}, σ_{0})-incomplete pre-absorbing labyrinth (L_{1}, L_{2}; y_{0}; α_{1}) for 𝔄_{q_{2}}, where L_{1} =⊣∗α_{1}|⊢ and L_{2} = ⟨ω_{0}⟩. Let L_{0} = ⟨ω_{0}⟩, L̃_{1} = L_{0}L_{1}L_{2}, and let

L′ = Cross(L̃_{1}, {x′_{0}, x′_{1}, x′_{2}, x′_{3}}),

where x′_{i} = (L̃_{1}; i) for every 0 ⩽ i ⩽ 3. As 𝔄 is irreducible and L′ ≅ ⊢ω_{0}α_{1}⊣, then from Propositions 3.1, 3.2, and 3.4 it follows that ω_{2} = dr(π(𝔄_{q_{1}}; L′), {x′_{3}}) = dr_{0}(π(𝔄_{q_{1}}; L′), \{x′_{3}\}) exists and ω_{2} ≠ \overline{ω_{0}} . Now, if ω_{2} ∈ \{ω_{0}, ω_{1}\}, then the ordered tuple (L_{0}, L_{1}, L_{2}; y_{0}) is a pre-absorbing labyrinth for 𝔄_{q_{1}}, and from Theorem 3.4 we get the contradiction. Hence ω_{2} = \overline{ω_{1}} .

Figure 4.

Let π(𝔄_{q_{1}}; L′) = (x̂_{0}, q̂_{0}), (x̂_{1}, q̂_{1}), … and t = tm(π(𝔄_{q_{1}}; L′), {x′_{3}}) (obviously, (x̂_{0}, q̂_{0}) = (x′_{0}, q_{1}) and x̂_{t} = x′_{3}). It is clear that x̂_{t−1} = x′_{2} and x̂_{t+1} = x′_{3} \overline{ω_{1}} . Let q_{3} = q̂_{t−1} and q_{4} = q̂_{t}. If the automaton 𝔄_{q_{4}} is not a snakelike σ_{0}^{−1} -walker, then Theorem 3.4 implies the existence of an (\overline{ω_{1}} , σ_{0}^{−1} )-incomplete pre-absorbing labyrinth (L_{3}, L_{4}; y_{1}; α_{2}) for 𝔄_{q_{4}}, where L_{3} =⊣ ∗α_{2}| ⊢ and L_{4} = ⟨ω_{0}⟩. Let L̃_{2} = L_{0}L_{1}L_{2}L_{3}L_{4} and L′′= Cross(L̃_{2}, {x_{i} | 0 ⩽ i ⩽ 5}), where x_{i} = (L̃_{2}; i) for every 0 ⩽ i ⩽ 5. It is obvious again that ω_{3} = dr(π(𝔄_{q_{1}}; L′′), {x_{5}}) = dr_{0}(π(𝔄_{q_{1}}; L′′), {x_{5}}) exists and ω_{3} ≠ \overline{ω}_{0}. Now, if ω_{3} ∈ \{ω_{0}, ω_{1}\}, then the 4-tuple (L_{0}, L_{1}L_{2}L_{3}, L_{4}; y_{0}) is a pre-absorbing labyrinth for 𝔄_{q_{1}}, and if ω_{3} = \overline{ω_{1}} , then the 4-tuple (L_{2}, L_{3}, L_{4}; y_{1}) is a pre-absorbing labyrinth for 𝔄_{q_{3}}. From Theorem 3.4 we get the contradiction and, consequently, we have to suppose that 𝔄_{q_{4}} is a σ_{0}^{−1} -walker. Put that β_{ω} := α_{0}(∗α_{1}∗)\overline{ω_{1}} .

It is clear that there exists a simple word γ_{1} [γ_{2}] over 𝔇 such that α_{1} = β_{e}γ_{1}(β_{w})^{−1} [α_{2} = β_{n}γ_{1}(β_{s})^{−1} ] is also a simple word over 𝔇, and L_{1} = ⟨α_{1}⟩ [L_{2} = ⟨α_{2}⟩] is an e-labyrinth [n-labyrinth]. Now from Proposition 3.8 we get that the pair (L_{1}, L_{2}) orients 𝔄_{q_{0}}. □

By way of illustration, let us prove an assertion which is an analogy for the plane labyrinths of the main theorem from [2].

Figure 5.

Theorem 3.8. For every initial automaton there exists a regular trap.

Proof. Let 𝔄_{q_{0}} be an initial automaton, and let 𝔄 be the corresponding noninitial automaton. Theorem 3.3 implies that there exists an irreducible or trivial automaton 𝔄′ and a mapping f :Q_{𝔄} → Q_{𝔄′} such that for every labyrinth L′ there exists a labyrinth L such that (𝔄′, L′) ⩽_{f} (𝔄, L). Let (K′; x_{0}) be the labyrinth given in Fig. 5, and let K be a labyrinth such that (𝔄′, K′) ⩽_{f} (𝔄, K). Also, let g be the corresponding mapping from the definition of ⩽_{f} for the pairs (𝔄, K) and (𝔄′, K′). Consider the automaton 𝔄′_{f(q_{0} )} . Now if 𝔄′ is trivial, then (K′; x_{0}) is a regular trap for 𝔄′_{f(q_{0} )} (take x_{4} as an exit) and, consequently, (K; g(x_{0})) is a regular trap for 𝔄_{q_{0}}. If 𝔄′ is irreducible, then by Theorem 3.7, there exist a snakelike e-labyrinth L_{1} and a snakelike n-labyrinth L_{2} such that the pair (L_{1}, L_{2}) orients 𝔄′_{f(q_{0} )} . Consider the labyrinth M′ = Cross(Δ(K′; L_{1}, L_{2})) and note that Δ(K′; L_{1}, L_{2}) ∈ L_{plwl} . Without loss of generality take that ψ_{𝔄′}(f(q_{0}), 𝔇) = n. But then for a σ_{0} ∈ {σ_{l}, σ_{r}} the automaton 𝔄′_{q_{1}}, where q_{1} = q(𝔄′_{f(q_{0} )} ; L_{1}, L_{2}), is a σ_{0}-walker with the guided vector n. So, (M′; x_{0}, x_{2}s) is a trap for 𝔄′_{f(q_{0} )} , and, because of Proposition 2.2, it is a regular trap for 𝔄′_{f(q_{0} )} . Now, since 𝔄′ ⩽ 𝔄, it follows that there exists a regular trap for 𝔄_{q_{0}}. □

By carefully analyzing the proof of Theorem 3.8 and the proofs of all the theorems cited in the proof, we come to the conclusion that for every initial automaton it is possible to construct a regular trap in an effective way.

References

1. Cl. E. Shannon, Presentation of a maze-solving machine, in: H. von Foerster, M. Mead, H. L. Teuber (eds.), Cybernetics: Circular Causal and Feedback Mechanisms in Biological and Social Systems, Transactions of the Eighth Conference (March 15–16, 1951), Josiah Macy, Jr. Foundation, New York, 1952, 173–180.

2. L. Budach, Automata and labirinths, Math. Nachr. 86 (1978), 195–282.

3. G. Kilibarda, V. B. Kudryavtsev, Š. Ušćumlić, Independent systems of automata in labyrinths, Discrete Math. Appl. 13(3) (2003), 221–256.

4. , Collectives of automata in labyrinths, Discrete Math. Appl. 13(5) (2003), 429–466.

5. �� ���������� ����� �������������� ������� �����������������, Diskretn. Mat. 3(3) (1991), 135–146.

6. �� �� ���������� �� �� ���������� �� �������� �������� � ������ ����������� ����� ������ ������� ���� ������� 1985.

Faculty of Project and Innovation Management (Received 25 12 2015) EDUCONS University Belgrade Serbia

    gkilibar@gmail.com