Finite automata and automatic structures

Get Complete Project Material File(s) Now! »

Chapter 2 Cayley graphs as automatic structures

In this chapter we give an introduction to automatic structures and Cayley automatic groups.

 Finite automata and automatic structures

Recall brie y the de nitions of nite automata and regular languages. For an introduction to nite automata and regular languages see, e.g., [22].
A nondeterministic nite automaton M over an alphabet is a tuple (Q; ; q0; F ), where Q is a nite set of states, q0 2 Q is an initial state, Q Q is a transition table, F Q is a subset of nal states. Let w 2 be a word w = 1 2 : : : n, i 2 for i = 1; : : : ; n. We say that the automaton M accepts the word w if there is a sequence of states q0; q1; : : : ; qn, qi 2 Q for i = 1; : : : ; n such that (qi 1; i; qi) 2 for i = 1; : : : ; n, and qn 2 F .
The language recognized by M is the set of all words accepted by M. A language L is called regular if it is recognized by a nite automaton over .
An automaton M = (Q; ; q0; F ) over an alphabet is called determin-istic if for every q 2 Q and 2 there exists at most one q0 such that (q; ; q0) 2 . Deterministic nite automata are equivalent to nondetermin-istic ones in the sense of computing power, i.e., deterministic and nondeter-ministic nite automata recognize the same class of regular languages.
A nite automaton can be thought as a one way read only Turing ma-chine. Recall that a two way nite automaton is a read only Turing machine which uses a constant amount of space on their work tape. Since a constant amount of space can be converted into a nite number of states of a Turing machine, then a two way nite automaton can be equivalently de ned as a read only one tape Turing machine.
A two way nite automaton is called deterministic if no more than one instruction is allowed for every con guration of the automaton. It appears that the classes of two way nite automata, two way deterministic nite au-tomata and nite automata are equivalent in the sense of computing power [23, Theorem VIII.1.5], i.e., all these classes recognize the same class of reg-ular languages.
A read only synchronous n tape Turing machine is a read only n tape Turing machine for which all n heads move synchronously either to the left or to the right. We suppose that an input for a n tape Turing machine is given as a n tuple of strings written on n tapes. If n > 1, then the class of read only synchronous n tape Turing machines is clearly weaker than the is de ned as the set of
class of read only n tape Turing machines in the sense of computing power. A read only one way synchronous n tape Turing machine is a read only synchronous n tape Turing machine for which the heads are allowed to move only to the right. By [23, Theorem VIII.1.5] we have that the class of read only synchronous n tape Turing machines is equivalent to the class of read only one way synchronous n tape Turing machines in the sense of computing power.
For a given nite alphabet , we denote by the alphabet = [f g, where 2= . À nite automaton over the alphabet n n f( ; : : : ; )g is called a synchronous n tape automaton. Due to [24] a synchronous n tape automaton is interpreted as a read only one way synchronous n tape Turing machine. The following de nition is originated from [25, 26].
De nition 2.1.1. Let (w1; : : : ; wn) 2 n be a n tuple of strings. The convolution of this tuple (w1; : : : ; wn) is the string of length maxfjwij; i = 1; : : : ; ng over the alphabet n n f( ; : : : ; )g such that the kth symbol is ( 1; : : : ; n), where i is the kth symbol of wi if k 6 jwij and if k > jwij.
The convolution R of a n ary relation R n convolutions of all n tuples from R.
We also denote a convolution (w1; : : : ; wn) as w1 wn. The set of nite automata recognizable (FA recognizable) relations is de ned as follows. De nition 2.1.2. We say that a n ary relation R n is FA recognizable if the convolution R is recognizable by a synchronous n tape automaton.
Recall some basic de nitions related to automatic structures. We refer the reader to [27, Chapters B and C] for more details.
n1 nk ‘1 ‘m ) is de ned by a domain A, A structure A = (A; R1 ; : : : ; Rk ; f1 ; : : : ; fm  atomic relations Rn1 ; : : : ; Rnk f‘1 ; : : : ; f‘m A, where each 1 k and functions 1 m on  R ni ; i = 1; : : : ; k is a ni ary relation and f ‘j ; j = 1; : : : ; m is a ‘j ary function.
We write an upper index in RiA to emphasize that it is a relation on A. A structure A can be uniquely associated with the relational structure AR by replacing each function f‘j ; j = 1; : : : ; m with its graph Graph(f‘j ) := f(x1; : : : ; x‘j ; y) j fj‘j (x1; : : : ; x‘j ) = yg.
De nition 2.1.3. We say that a relational structure A = (A; R1n1 ; : : : ; Rknk ) is automatic over a nite alphabet if the domain A and the atomic relations Rini ni ; i = 1; : : : ; k are FA recognizable.
An A formula (x1; : : : ; xk) is a formula for which all non logical sym-bols belong to the signature A. A relation R of arity n is rst order de n-able in a structure A if there exists a A formula (x1; : : : ; xn; y1; : : : ; ym) and m elements c1; : : : ; cm 2 A such that (x1; : : : ; xn) 2 R i A (x1; : : : ; xn; c1; : : : ; cm). The formula (x1; : : : ; xn; y1; : : : ; ym) is called a rst order de nition in A of the relation R. The following theorem is due to [4, 28].
Theorem 2.1.1. If A is an automatic structure over then there is the algorithm that for a relation R de ned by a rst order formula (x1; : : : ; xn; y1; : : : ; ym) in A with parameters c1; : : : ; cm constructs a n tape synchronous automaton recognizing R.
De nition 2.1.4. We say that two relational structures A = (A; R1A; : : : ; RkA) and B = (B; R1B; : : : ; RkB) of the same signature are isomorphic if there exists a bijection ’ : A ! B such that for every i = 1; : : : ; k, (x1; : : : ; xn) 2 RiA i (’(x1); : : : ; ’(xn)) 2 RiB, where n is the arity of Ri.
The isomorphism type of a structure A is the equivalence class of all struc-tures that are isomorphic to A. If one admits that ’ : A ! B is an embedding such that for every atomic relation R of some arity n: (x1; : : : ; xn) 2 RA i (’(x1); : : : ; ’(xn)) 2 RB then A is called a substructure of B.
De nition 2.1.5. We say that a structureA = (A; Rn1 ; : : : ; Rnk ; f‘1 ; : : : ; f‘m ) is automatic (or FA presentable) if the relational structure AR = (A; R1n1 ; : : : ; Rknk ; Graph(f1‘1 ); : : : ; Graph(fm‘m )) is isomorphic to a structure B which is automatic over some nite alphabet .
The rst order theory of a structure A is the set of all rst order sentences that are true in A. A rst order theory is called decidable if there is an algorithm that decides whether or not a given rst order sentence belongs to the theory. As a corollary of Theorem 2.1.1 we obtain the following theorem.
Theorem 2.1.2. The rst order theory of an automatic structure A is de-cidable.
We say that an equivalence relation A A on a structure A = (A; R1A; : : : ; RnA) is a congruence relation if for every atomic relation RA of some arity m the following holds: if (xi; yi) 2 for all i = 1; : : : ; m, then (x1; : : : ; xm) 2 RA i (y1; : : : ; ym) 2 RA. A congruence relation on a structure A de nes the quotient structure A= of the same signature.
Let (x1; : : : ; xk) and i(y11; : : : ; yk1; : : : ; y1ri ; : : : ; ykri ); i = 1; : : : ; n be A formulas that de ne the structure (B; RrB1 ; : : : ; RrBn ), where B = B i for f(x1; : : : ; xk)jxi 2 A; A(x1; : : : ; xk)g and Rri are de ned by  i = 1; : : : ; n, respectively. If then there is a congruence relation on the structure (B; RrB1 ; : : : ; RrBn ) de ned by a A formula (x1; : : : ; xk; y1; : : : ; yk), then we say that the structure (B; RB ; : : : ; RB )= is rst order de nable in r1 rn
A. We say that a structure C is rst order interpretable in A if it is iso-morphic to a structure which is rst order de nable in A. As a corollary of Theorem 2.1.1 we obtain the following theorem (cf. [4, 29]).
Theorem 2.1.3. If a structure A is automatic and B is a rst order inter-pretable structure in A, then B is automatic.
As a corollary of Theorem 2.1.3 we obtain the following proposition.
Proposition 2.1.1. Let A be an automatic structure. Then a substructure of A with a rst order de nable domain is automatic. The structure A= de ned by a rst order de nable congruence relation is automatic.
By Theorem 2.1.3 we obtain the following proposition (cf. [4, 29]).
Proposition 2.1.2. Let A = (A; R1; : : : ; Rn) be a structure. Let rj be the arity of Rj for j = 1; : : : ; n. Suppose that there exist a regular language L, a surjective map : L ! A and FA recognizable relations L L2, Lj Lrj , j = 1; : : : ; n such that the following properties hold:
(x1; x2) 2 L i (x1) = (x2);
(x1; : : : ; xrj ) 2 Lj i ( (x1); : : : ; (xrj )) 2 Rj for j = 1; : : : ; n. Then the structure A is automatic.
On the other hand, if a structure A = (A; R1; : : : ; Rn) is automatic then the condition of Proposition 2.1.2 is true. Therefore, this condition gives an equivalent de nition of automatic structures (cf. [4]). The map
: L ! A and the regular languages L; L1; : : : ; Ln together with a collection of automata recognizing them constitute an automatic representation of the structure A.
We use 91 and 9(k;m) to denote the existential quanti ers interpreted as there exist in nitely many and there exist k modulo m many, respectively. Let us give two simple examples of using the quanti ers 91 and 9(k;m). Consider the structure (N; <). The rst order de nition 9(0;2)y(y < x) describes the unary relation R(x) N which contains all even natural numbers. Consider a graph V; E). The rst order de nition 91y(E(x; y)) describes the unary relation R(x) V that contains all vertices of V; E) for which the number of adjacent vertices is in nite.
Theorem 2.1.1 can be generalized as follows (cf. [12, 29]).
Theorem 2.1.4. Let A be an automatic structure over . For a relation R given by a rst order de nition (x1; : : : ; xn; y1; : : : ; ym) in A with parameters c1; : : : ; cm and, probably, containing the quanti ers 91 and 9(k;m) there exists the algorithm which constructs a n tape synchronous automaton recognizing R.
Recall some characterization theorems for FA recognizable relations and automatic structures. For a given non empty set A f1; : : : ; ng we denote by A the subset A = f( 1; : : : ; n)j i 6= i i 2 Ag n
. There is the following decomposition theorem [24].
Theorem 2.1.5. A relation R n is FA recognizable i R is a nite union of products of the form: R 0 :::R k , where each R i n i = 0; : : : ; k Ai for is FA recognizable and Ak A0 f1; : : : ; ng.
For = f0; : : : ; k 1g let Wk be the structure Wk = ( ; ( a)a2 ; p; e‘), where a(u) = ua, u p v if u is a pre x of v, e‘(u; v) if u and v have the same length. The structure Wk is automatic. The theorem below provides the characterization of FA recognizable n ary relations R n, j j > 2 in terms of their de nability in Wk (cf. [25, 26]).
Theorem 2.1.6. For k ary alphabet with k > 2 a relation R n is FA recognizable i it is rst order de nable in the structure Wk.
Let be a unary alphabet, j j = 1. Let us identify and N in a natural way. We denote by p the congruence relation modulo p on N. The theorem below provides the characterization of FA recognizable n ary relations R n in terms of their de nability in the structure (N; 6; ( p)p2N) (cf. [29, 30]).
Theorem 2.1.7. A relation R n, j j = 1, is FA recognizable i it is rst order de nable in the structure (N; 6; ( p)p2N).
The theorem below provides the characterization for automatic structures in terms of their interpretability in Wk (cf. [31]).
Theorem 2.1.8. A structure A is automatic i it is rst order interpretable in Wk for some, equivalently all, k > 2.

0 Preface 
1 General Introduction 
2 Cayley graphs as automatic structures 
2.1 Finite automata and automatic structures
2.2 Cayley automatic groups
3 The BaumslagSolitar groups 
3.1 The BaumslagSolitar groups and HNN extensions
3.2 The BaumslagSolitar groups are Cayley automatic
4 Wreath products of groups 
4.1 Wreath products: short introduction
4.2 The lamplighter group Z2 o Z
4.3 Wreath products G o Z
4.4 The wreath products Z2 o Fn
4.5 Wreath products G o Fn
4.6 The wreath product Z2 o Z2
5 NonCayley automatic transitive graphs 
5.1 Examples of automatic nonCayley transitive graphs
5.2 The DiestelLeader graph is automatic
6 On characterizations of Cayley automatic groups
6.1 Turing transducers of the class T
6.2 Numerical characteristics of Turing transducers
6.3 Asymptotic behavior of growth and Flner functions
6.4 Random walk and average length growth functions
7 Conclusion and open problems 
Bibliography
GET THE COMPLETE PROJECT