Lobachevskii Journal of Mathematics Vol. 9, 2001, 7 – 14 \begin{matrix}c \\ ◯ \end{matrix}V.R. Bairasheva

V.R. Bairasheva

ATOMS IN THE STRUCTURE OF DEGREES OF AUTOMATA TRANSFORMATIONS AND THEIR MONADIC THEORIES

(submitted by M.M. Arslanov)

Abstract. The existence of atoms of automaton reducibility degrees structure with essential different properties is proved. In the proof the priority method from the theory of recursive funtions was used.

Introduction

G.Reina defined in [1] the notion of reducibility of superwords (i.e. infinite sequences of characters) by means of finite automata. The corresponding equivalence classes of superwords are called degrees of automata transformations. These degrees, ordered in the natural way by the reducibility relation, forms a partially ordered set V. V has the minimal element, denoted by 0 - it is the degree, consisting of the periodic superwords.

As in general study of structures of degrees relative to different reducibilities [2], in the case of study of the structure V significant interest cause elements, positioned the most close to 0, i.e. atoms. In [1] there was shown existence of atoms in the structure V. The superwords, belonging to the atoms constructed up to now, are close to periodic sequences in the different meaning of the word: namely, they have structure analogous to the structure of almost periodic sequences in the sense of [4].

As periodic superwords have decidable monadic theory [5], it is natural to ask if the monadic theory of superwords, belonging to atoms, is decidable too.

In this article there are constructed examples of superwords, belonging to atoms and having decidable as well as undecidable monadic theories.

Key words and phrases. finite-state automata, reducibility, atoms, priority method.

This research was supported by the Russian Foundation for Basic Research, Grant N 00-01-00526 and by the RF Educational Ministry (Sankt-Petersburg Grant Center).

Let’s start from some necessary definitions. We consider superwords, i.e. infinite sequences of symbols, belonging to some alphabet P. All relevant information from the finite automata theory may be found in [6]. A finite automaton is initial, if some initial state is fixed. By T(s,X)=Y we denote the fact, that automaton T, starting to work in the state s, transforms the (super)word X into the (super)word Y.

Definition 1. Superwords X and Y are equivalent, if there exist finite automata T and T’ with initial states s and s’, respectively, and (finite) words A and A’, A ∈ P* and A’∈ P* ( * - )such that T(s,X)=AY and T’(s’,Y)=A’X. The class [X] of the superwords, equivalent to some superword X, is called degree of automata transformations.

Definition 2. Degree [X] is reducible to degree [Y], [X]≤[Y], if there exists a finite automaton T with initial state s and a word A such that T(s,Y)=AX.

Further we use some enumeration T_{1},T_{2,:}of all finite automatons.

Let X be a superword. For natural numbers n and m X[m, m+n) denotes the subword of X, which starts from the position m and have the length n.

Definition 3 [4]. A superword X is almost periodic, if for any word A there exists a number Δ_{A}, satisfying one of the following conditions ( which we’ll call further on the almost periodicity conditions):

1) all occurrences of A in X belong to the interval X[0, Δ_{A}]

2) each interval X[m, m+Δ_{A}], m ∈ N, includes some occurrence of A.

The mapping, determining for each A the corresponding number Δ_{A}, is called almost periodicity pointer for the superword X. If this mapping is a computable function, we call X effectively almost periodic.

Following [5], let’s define the metalanguage U, which is a logical language for describing properties of superwords.

Letters, belonging to the alphabet of superwords, forms countable list of the language constants. Variables with domain, consisting of all superwords in some alphabet, are denoted by x, y, : They are called senior variables. Apart them, there are also junior variables, denoting natural numbers, the constant 1 and the functional symbol τ, denoting successor function, τ(t)=t+1, t ∈ N. Terms are expressions of the form 1, t, τ(t), τ(τ(t)),: etc., which are more conveniently written in the traditional form 1, t+1, t+2,: etc. Atomic formulas have the form x(n)=a and express the following statement: the n-th symbol of the word X is a. The language U also includes traditional notation for the common logical operations and quantifiers, binding senior and junior variables. The notion of logical formula is also introduced in the traditional way.

Definition 4 [5]. For a superword X, the set U(X) of all formulas of the language U, containing the single variable x and evaluating to true after substituting the variable x with X, is called monadic theory of X.

To characterize a superword X, it’s important to answer the question, if the monadic theory U(X) is decidable.

§1. Atoms with decidable monadic theory

Theorem 1. There exists a superword X with decidable monadic theory, degree [X] of which is an atom of the structure V.

Proof. Let’s construct the needed superword X in the alphabet {0,1}. To do this, we’ll construct at first the sequence of words I_{i}, i ∈ N, where for each i I_{i}is a proper initial segment of the following word I_{i+1}. The superword X will be defined as the limit of the sequence I - i.e. the only superword, containing each I_{i}, i ∈ N, as an initial segment.

Using induction by i, i ∈ N, we’ll define the words I_{i}, together with some words A_{i}, and B_{i}, satisfying the following conditions:

1) A_{1}begins from 0, B_{1} begins from 1 and they have the equal length.

2) Each word A_{i+1}, (also B_{i}) is a sequence of copies of the previous words A_{i}, and/or B_{i}, beginning from A_{i} ( B_{i}, respectively).

3) A_{i+1} and B_{i+1}have the equal length, greater than i.

4) A_{i+1} and B_{i+1}is not a part of any periodic sequence with the period i.

5) I_{i+1} consists of I_{i}and the following copies of the words A_{i} and/or B_{i}.

6) If input I_{i} moves the initial automaton T_{i}to some final state s, then T_{i}returns to the final state s, when it accepts as an input word the word A_{i} , as well as the word B_{i}.

Now let’s describe a method of constructing the words with the desired properties. The method is a two-parametric generalization of construction, given by G.Reina in [1].

Set I_{0}=∅, A_{0}=0, B_{0}=1.

On the step i+1 the words I_{i},A_{i}, B_{i} are already constructed. Define A_{i}’=α_{1}(A_{i}, B_{i}) and B_{i}’=α_{2}(A_{i}, B_{i}), where α_{1}(A_{i}, B_{i})and_{α2}(A_{i}, B_{i}) are words of the equal length, consisting of the words A_{i} and B_{i}and beginning from the words A_{i} and B_{i}, respectively. Thus, α_{1}and_{α2}are some parameter functions here.

Let (T,s_{0}) be (i+1)-th initial automaton with initial state s_{0} and, for any state s of T, ¡s¿ is a set of all states, which are final for some words, consisting from the blocks A_{i}’ and B_{i}’. Also, let s_{1}be the state, to which the block I_{i}moves the automaton T from the initial state s_{0}. Choose s_{2}, s_{2∈}¡s_{1}¿,for which the cardinality of ¡s_{2}¿ is minimal. Then s_{2∈}¡s_{2}¿. Define I_{i+1}as the word, which moves automaton T from the state s_{0}to the state s_{2}. By definition, I_{i+1}consists of I_{i}and the following block, containing just the words A_{i}’ and B_{i}’.

The lengths of the words A_{i}’ and B_{i}’ are not greater than i and these words differ in their first symbols. Thus, if the word A_{i}’A_{i}’ is a part of some periodic sequence with period i, then A_{i}’B_{i}’ is not. Let H be those from the two words, which is not a part of the periodic sequence and s_{A}be the state, to which the word H moves the automaton T from the state s_{2}. As s_{2}is minimal by definition and s_{A∈}¡s_{2}¿⊆¡s_{1}¿, then ¡s_{A}¿=¡s_{2}¿. Hence, s_{2∈} ¡s_{A}¿.

Let A_{i+1}’ be the word, consisting of the blocks A_{i}’ and B_{i}’ and beginning from the block I_{i}, which moves the automaton (T, s_{2}) to the final state s_{2}. The length k of A_{i+1}’ is greater than i+1 and A_{i+1}’ is not a part of any periodic sequence with period i. The word B_{i+1}’ is constructed in the same way, with the only exception, that it begins from B_{i}’. Let l be the length of B_{i+1}’. Define A_{i+1}” as l copies of the block A_{i+1}’ and B_{i+1}” as l copies of the block B_{i+1}’. Finally, define A_{i+1} as β_{1}(A_{i+1}”, B_{i+1}”) and B_{i+1} as β_{2}(A_{i+1}”,B_{i+1}”), where β_{1}, β_{2}are another parameter functions, satisfying the same conditions, as the functions α_{1} and α_{2}above.

It’s clear, that the words A_{i+1} and B_{i+1}transfer state s_{2}to itself, begin respectively from 0 and 1, and have the equal length, i.e. satisfy the desired properties 1)-6).

Let’s prove, that the superword X, X=lim {I_{i}: i∈N}, belongs to some atom of the structure V. First of all, X is not periodic, hence it doesn’t belong to the minimal degree 0. It follows from the fact, that for any n, n∈N, the blocks of X A_{n+1}and B_{n+1,}whichfollow the initial segment I_{n}, can’t be parts of any periodic sequence with period n.

Suppose now that [X]≥[Y], for some sequence Y. Let i be an ordinal number of the initial automaton (T, s_{0}), which transforms X to Y.

By construction X is a sequence of copies of the blocks A_{i}and B_{i}of some length k_{i}, following the initial block I_{i}. Moreover, T moves to the same state - say, s - every time when one of the blocks A_{i}and B_{i}begins. Hence, the output sequence Y consists of copies of just two blocks - say, C and D, (which are images of A_{i} and B_{i}, respectively), having some equal length k. If the words C and D are equal, then Y is periodic, with some foreperiod, and the degree [Y] is minimal. If C and D are not equal, then there evidently exists an automaton, which transforms C to A and D to B. Hence, in this case [Y]≥[X], and [Y]= [X]. So, [X] is an atom.

For the final definition of the superword with the desired properties, it is sufficient to choose the following values of the parameter functions used: α_{1}(A,B)=AABBA, α_{2}(A,B)=BBAAB, β_{1}(A,B)=A and β_{2}(A,B)=B. We’ve already proved, that degree of the superword X constructed is an atom. Let’s prove now, that it is effectively almost periodic.

Take any word C. Find such numbers i and k_{i}, that ?C?¡ k_{i}=?A_{i?}=?B_{i?}. The following cases are possible:

1. C is a subword of A_{i}or B_{i}.

2. C is not a subword of A_{i}orB_{i}, but it is a subword of some word XY, where X∈{A_{i}, B_{i} }and Y∈{A_{i}, B_{i} }.

3. Neither of cases 1 and 2 holds.

Let’s consider each of these cases.

1. By our choice of parameter functions, both A_{i}andB_{i}are contained in A_{i+1},as well as inB_{i}. Then, any subword of X , having the length 2?A_{i+1?} and situated after the initial segment I_{i+1}, contains either A_{i+1}orB_{i+1} as an subword. Hence, each word of this length, situated after I_{i+1}, contains C. Thus, to satisfy the almost periodicity conditions, it’s sufficient to set Δ_{c}=2?A_{i+1?}+? I_{i+1?}.

2. If C is a subword of some XY, where X∈{A_{i}, B_{i} }and Y∈{A_{i}, B_{i} }, then, by definition of A_{i}’ and B_{i}’, the word XY and hence also C are subwords of A_{i+1} and B_{i+1}. So, in this case Δ_{c}can be also set equal to 2?A_{i+1?}+? I_{i+1?}.

3. In this case C may be found in X just within the initial segment I_{i}, so we can set Δ_{c}=?I_{i?}.

According to the construction, the numbers k_{i}=?A_{i?}can be found effectively, hence the same is true for the minimal k_{i,}such that_{?}C?¡ k_{i}. Comparing C with the words A_{i}, B_{i}, A_{i}A_{i}, A_{i}B_{i}, B_{i}A_{i} and B_{i} B_{i,}one can effectively determine, which of the three cases considered above holds. Thus, Δ_{c}can be found effectively for any C and the superword X is effectively almost periodic.

It’s shown in [5], that effectively almost periodic superwords have decidable monadic theories. Thus, the theorem is proven.

§2. Atoms with undecidable monadic theory

Existence of atoms with undecidable monadic theory can be easily proved unconstructively using cardinality arguments. It’s proved in [7], that there exists the continuum number of atoms. Hence, there exists an non-recursive superword, belonging to an atomic degree. On the other hand, if a superword X - say, in the alphabet {0,1}- has decidable monadic theory, then, applying the decision procedure to the formulas X(1)=0, X(2)=0, etc., we can obtain an algorithm of determining each letter of the superword X, i.e. X is recursive.

It turned to be significantly harder to prove that there exists a recursive superword, which has undecidable monadic theory and belongs to an atomic degree. There’s been no success yet in proving the fact using methods common in the finite automata theory. We’ll prove it, using the priority method developed in the algorithms theory.

Theorem 2. There exists a recursive superword with undecidable monadic theory, degree of which is an atom of the structure V.

Proof. For a given superword X decidability of its monadic theory means, that there exists an algorithm determining if an arbitrary formula with a single free senior variable is true when this variable is substituted by X. Consider an enumeration of all formulas with a single free senior variable z (as the formulas are finite objects, an effective enumeration can be chosen): F_{1}(z), F_{2}(z),: Let φ_{0}, φ_{1},: be some Gdel enumeration ([2]) of all partially recursive functions (or, briefly, p.r.f.’s). Further on, by φ_{n}(F_{k}(z)) we mean φ_{n}(k), i.e. the value of the n-th p.r.f. on the ordinal number of the formula F_{k}.

Our aim is to build a superword X (in the alphabet {0,1}) such that ∀n ∃k ( ( φ_{n}(F_{k}(z))∉ {0,1} ) ∨ ( (φ_{n}(F_{k}(z))=1 ⇔ F_{k}(X) is false) & (φ_{n}(F_{k}(z))=0 ⇔ F_{k}(X) is true) ) ) That would mean that no algorithm (i.e. a p.r.f. with some number n) can

give decision procedure for the monadic theory of the superword X.

Our construction uses a list of p.r.f.’s Φ, which is at the very beginning equal to the list of all p.r.f.’s, Φ={φ_{0},φ_{1},:}. During construction some functions will be deleted from the list. Besides, some functions will be marked with a symbol + ; after that, this marker can be removed, then placed once again etc.

On each step of construction several steps in computation of the functions φ_{0},φ_{1},: are made. Denote by φ_{i}^{j}the finite function, which is the result of making j steps in the computation of the p.r.f. φ_{i}.

Now, let’s describe the construction itself.

Step 0. Set I_{0}=∅, A_{0}=0, B_{0}=1, D_{0}=A_{0} and the formula U^{0}(z) be

∀ s ∃ t ( (t≥s) & (z(t)=0) & (z(t+1)=0) & (z(t+2)=0)) As it’s shown in [6], the predicate t≥s can be expressed by a formula of

the metalanguage U. Hence we can assume U^{0}(z) to be the formula of this language. Informally, U^{0}(z) means that the subword D_{0}D_{0}D_{0} can be found infinitely many times in the superword z.

Step n. The words I_{n−1}, A_{n−1}, B_{n−1}, D_{n−1} are already built and the formulas U^{0}(z),:,U^{n−1}(z) are already defined up to this step. Make n steps in com-

putation of the functions φ_{0}(U^{0}(z)),:,φ_{n−1}(U^{n−1}(z)), which still belong to the list Φ and are not marked by +.

Let i, i≤n, be the minimal from the numbers j such that φ_{j}^{n}(U^{j}(z)) is defined (if any of such j exists). The following 4 cases are possible:

1. If i is undefined, then build the words I_{n}, A_{n} and B_{n} as in the previous theorem, let D_{n}=A_{n}and define the formula U^{n}(z) as follows: if D_{n}D_{n}D_{n}=a_{i(1)}:a_{i(m)}, where a_{i(j)∈}{0,1}, j∈ [1,m], then U^{n}(z) is the formula

∀ s ∃ t ( (t≥s) & (z(t)= a_{i(1)}) & : & (z(t+2)= a_{i(m)}) )

Go to the next step.

2. If i is defined and the corresponding value φ_{i}(U^{i}(z))∉{0,1}, then remove φ_{i}from the list Φ - we’ll never consider φ_{i} again, as it is knowingly can’t be the function, providing a decision procedure for the monadic theory of the superword X. Define I_{n}, A_{n} and B_{n}and U^{n}(z) as in the previous case and go to the next step.

3. If φ_{i}(U^{i}(z))=0, then the i-th algorithm potentially can answer if the monadic theory is decidable for the superwords, in which the subword D_{i}D_{i}D_{i}can’t be met infinitely often. Redefine A_{i}as A_{i}’, A_{i}’=β_{1}(A_{i},B_{i})=(A_{i})^{4},and B_{i} as B_{i}’, B_{i}’=β_{2}(A_{i},B_{i})= B_{i}(A_{i})^{3}. Set I_{i}=I_{n−1}, mark the function φ_{i}with the symbol +, remove this marker from all the functions φ_{j}with j¿i and go to the step i+1.

4. If φ_{i}(U^{i}(z))=1, then redefine A_{i} as A_{i}’, A_{i}’=β_{1}(A_{i},B_{i})=A_{i}B_{i}, and B_{i} as B_{i}’, B_{i}’=β_{2}(A_{i},B_{i})= B_{i}A_{i} and set I_{i}=I_{n−1}. As in the previous case, mark the function φ_{i}with the symbol +, remove this marker from all the functions φ_{j}with j¿i and go to the step i+1.

In the cases 3 and 4 the step n remains incomplete in the sense that I_{n}, A_{n}, B_{n}, D_{n} and U^{n}remain undefined. While going back to the step i+1, I_{i}, A_{i}, B_{i} have the redefined values they got on the step n, but D_{i} and U^{i} remain the values they got on the step i.

Description of construction is completed.

For any function the marker + can be placed and removed no more than finitely many times; it follows from the fact, that this marker can be removed just when the marker is assigned to some function with a smaller number and there are finite number of the latter.

So it’s clear that each step i will be passed just finitely many times, namely - up to the time, when all the functions φ_{0},:,φ_{i−1}that potentially can be computed on the arguments used in construction will get their values and when all of them will be finally assigned the + marker, which will be not removed on the future steps. Denote the corresponding limit values of I_{n}, A_{n}, B_{n}, D_{n} and U^{n}by \underline{I}_{n}\underline{,} \underline{A}_{n}\underline{,} \underline{B}_{n}\underline{,} \underline{D}_{n}and \underline{U}^{n}.

By construction in the limit each function φ_{i}will be either deleted from the list, undefined on the argument \underline{U}^{i}(z) or assigned the + marker.

Set X=lim\{ \underline{I}_{n}: i ∈ N\}. Then there exists an increasing sequence k of natural numbers k_{1}¡ k_{2}¡:, such that for any natural j X is a concatenation of some initial segment \underline{I}_{j}and copies of the words \underline{A}_{j}and \underline{B}_{j} , having the length k_{j}. As it’s easily seen from construction, the words \underline{I}_{j},\underline{A}_{j}and \underline{B}_{j}satisfy the conditions 1-6 and hence [X] is an atom.

For instance, let’s prove the said for the condition 4. By construction each block A_{i}is initially built when the cases 1 and 2 are valid; then, it can be modified if the cases 3 and 4 become valid. But when the cases 1 and 2 are in place, the blocks A_{i}and B_{i}are built as they were built in the theorem 4, which guarantees the condition 4 to be satisfied. When the cases 3 and 4 are in place, the new versions of blocks A_{i′} and B_{i′} are defined as β_{1} (A_{i},B_{i})=(A_{i})^{4} and β_{2}(A_{i},B_{i})= B_{i}(A_{i})^{3}, in terms of their old versions. If, by induction, the latter weren’t subwords of any periodic sequence with the period i-1, then the same is true for the new versions of the blocks. Hence the limit versions \underline{A}_{i}and \underline{B}_{i} of these blocks also can’t be parts of any (i-1)-periodic sequence, i.e. the condition 4 is satisfied.

Suppose now that U(X) is decidable. Then there exists a total recursive function f such that ∀ i ( (f(F_{i})=1 ⇔ F_{i}is true) & (f(F_{i})=0 ⇔ F_{i}is false) ). Let k be a ordinal number of f in the accepted enumeration and let j be the minimal number such that on the step j f, f=φ_{k}, doesn’t have the + marker, φ_{k}has been already computed and besides all the functions with smaller numbers either will be never computed on arguments Fl, l¡=k, on the later step or they have got the + marker, which will be never removed later on. By other words, it means that after the step j there will be no returns to the steps with numbers smaller than k.

If f(U^{k}(z))=1, then according to construction (see case 4) in the superword X, starting from some position (namely, after \underline{I}_{k}), there are no inclusions of the word D_{k}D_{k}D_{k}and hence U^{k}(X)is false.

If f(U^{k}(z))=0, then in the superword X there are infinitely many inclusions of the word D_{k}D_{k}D_{k}, contained in \underline{A}_{k}and \underline{B}_{k} and hence U^{k}(X) is true.

Thus any algorithm fails at least on one formula. As X is recursive, the theorem is proven.

References

1. Hartley Rodgers, Jr. Theory of recursive functions and effective computability. McGraw-Hill Book Company, 1967.

2. G.Reina. Degrees of finite-state transformations. Kibernet. sb., no.14,1977, pp.95-106.

2. V.R. Bairasheva. Initial segments of automaton transformation degrees. The 8-th all-union conference on problems of theoretical cybernetics. Gorky University Press, 1988, pp. 15-17

4. K. Jacobs. Maschinenerzeugte 0-1-Folgen. In: Selecta Mathematica II, K.Jacobs ed., Berlin: Springer-Verlaag, 1970.

5. A.L. Semenov. Logical theories of functions of a single natural argument. Izvestya AN SSSR, Mathematical series, 1983, vol. 47, no.3, pp. 1175-1195

6. B.A. Trahtenbrot, Y.M. Barzdin. Finite automata. Moscow, Nauka Publishing House, 1970, 400 pp.

7. V.R. Bairasheva. Degrees of random sequences under automaton transformations. Ph D thesis. Kazan State University, 1990.

14 V.R. BAIRASHEVA

Kazan State University, Dep. of Theoretical Cybernetics, Kremlevskaya 18, Kazan, 420008, Russia E-mail address: solovyev@mi.ru

Received December, 1, 2001