[PDF] LOGIC AND p-RECOGNIZABLE SETS OF INTEGERS 1 Introduction

View - Download LOGIC AND p-RECOGNIZABLE SETS OF INTEGERS 1 Introduction

Previous PDF

Next PDF

LOGIC ANDp-RECOGNIZABLE SETS OF

INTEGERS

Veronique Bruyere

Georges Hansel Christian Michaux

y

Roger Villemaire

z

Abstract

We survey the properties of sets of integers recognizable by automata when they are written inp-ary expansions. We focus on Cobham's theorem which characterizes the sets recognizable in dierent basespand on its generaliza- tion toN m due to Semenov. We detail the remarkable proof recently given by Muchnik for the theorem of Cobham-Semenov, the original proof being published in Russian.

1 Introduction

This paper is a survey on the remarkable theorem of A. Cobham stating that the only sets of numbers recognizable by automata, independently of the base of repre- sentation, are those which are ultimately periodic. The proof given by Cobham, even if it is elementary, is rather dicult [15]. In his book [24], S. Eilenberg proposed as a challenge to nd a more reasonable proof. Since this date, some researchers found more comprehensible proofs for subsets ofN, and more generally ofN m .Themore recent works demonstrate the power of rst-order logic in the study of recognizable sets of numbers [54, 49, 50]. One aim of this paper is to collect, from Buchi to Muchnik's works [9, 54], all the base-dependence properties of sets of numbers recognizable by nite automata, with some emphasis on logical arguments. It contains several examples and some logical proofs. In particular, the fascinating proof recently given by A. Muchnik is detailed This work was partially supported by ESPRIT-BRA Working Group 6317ASMICSand Co- operation Project C.G.R.I.-C.N.R.S.Theorie des Automates et Applications. y Partially supported by a F.N.R.S. travel grant. The author thanks for its hospitality the Department of Mathematics and Computer Science of UQAM and the Centre Ricerca Matematica at Barcelona. z The author thanks for its hospitality the team of Mathematical Logic at Paris 7 and also the Department of Mathematics and Computer Science of UQAM for nancial support. Received by the editors November1993, revised February 1994.

Communicated by M. Boa.

AMS Mathematics Subject Classication : 11B85, 03D05, 68R15, 68Q45. Keywords : innite words,p-recognizable sequences, nite automata, rst-order denabil- ity, formal power series.

Bull. Belg. Math. Soc. 1 (1994), 191{238

192V. Bruyere - G. Hansel - C. Michaux - R. Villemaire

and simplied. It states Cobham's theorem and the generalization of Semenov to N m . The paper also contains bibliographic notes on the history of the results. This survey is born of several lectures given by the authors, respectively V. Bruyere, 29 April 93 - Universite Libre de Bruxelles, G. Hansel, 26 April and 3 May

93 - Universite Paris 6, C. Michaux, 2 September 92 - Universite de Mons-Hainaut

and R. Villemaire, 23 November 92 - University McGill, 3 December 92 - Universite UQAM. It addresses readers accustomed with automata, but less familiar with rst- order logic. It may be read in dierent ways, depending on the interests of the reader. The paper is arranged in the following way. It begins with a brief section on automata and a lesson of logic to make the reader more familiar with rst-order structures, denable sets and decidable theories. Next, Section 4 deals withp-recognizable sets of numbers, i.e., sets of numbers whosep-ary expansions are recognizable by a nite automaton. Various characteri- zations ofp-recognizability are related in Theorem 4.1 : iterated uniform morphisms, algebraic formal power series, and denability by rst-order formulae. Section 4 is centered around these four models ofp-recognizability. It begins and ends with two generic examples. It also contains some bibliographic notes related to Theorem 4.1, as well as notes about the automata associated withp-recognizable sets. Section 5 is in the same spirit but forp-recognizable subsets ofN m . The four models still hold and are again equivalent (Theorem 5.1). Among the dierent characterizations ofp-recognizability, Section 6 emphasizes the logical one. The currently simplest proof of this equivalence is given, following the references [40, 74]. At the origin, it was proved by R. Buchi in his paper [9]. Some corollaries of decidabilityand nonp-recognizability are easily derived, together with a powerful tool for operations preservingp-recognizability (Corollaries 6.2, 6.3 and 6.4). Next, Section 7 studies the dependence ofp-recognizability on the base of repre- sentation. In particular it contains Cobham's theorem (Theorem 7.7). It shows that there are essentially three kinds of subsets ofN m : the sets recognizable in every base p, the sets recognizable in certain bases only, and the sets recognizable in no base. The rst class is quite restricted, as it is limited to the rational sets of the monoid (N m ;+). Whenm= 1, it is precisely the ultimately periodic sets. It is rather easy to see that ultimately periodic sets arep-recognizable for every integerp>2, but the converse relies on the deep theorem of Cobham. As forp-recognizable sets, sets recognizable in every base are characterized in various ways (Theorems 7.3 and 7.4), including a logical characterization and a ne denability criterion found recently by A. Muchnik [54]. Muchnik's criterion is at the heart of his remarkable proof of

Cobham's theorem overN

m , it also allows one to decide whether ap-recognizable set ofN m is recognizable in every base (Proposition 7.6). Section 8 is devoted to Muchnik's proofs of the denability criterion and of the theorem of Cobham-Semenov overN m . The original proof is in Russian. We follow it, simplifying some parts and detailing others. The last section is a brief introduction to related works and references. The list is certainly not complete; however it may give a avour of connected research works.

Logic andp-recognizable sets of integers193

2 Preliminaries

We brie

y recall some denitions about automata, automata with output and ra- tional operations. These notions are well detailed in [24, 43, 58].

The setsAandBare nitealphabets.WedenotebyB

the set of allwords written withlettersofB, including theempty word.SetB is a monoid called thefree monoid generated byB, with concatenation as product operation and as neutral element. The symboljwjdenotes thelengthof the wordw2B and w R thereverseofw.Inthispaper,AandBare often nite subsets of the set

N=f0;1;2;:::gof natural numbers.

AnautomatonA=(Q;I;F;T) is a graph with a setQof vertices orstatesand asetTQBQof edges ortransitionslabelled by an alphabetB.SetIQ is the set ofinitialstates andFQthe set ofnalstates. A wordw2B is accepted(orcomputed)byAif it is the label of some path inAbeginning with an initial state and ending with a nal state. We say thatLB isrecognizableif it is the set of words computed by someniteautomaton, i.e., withQnite. An automatonAisdeterministicif it has a unique initial state and ifTis a (partial) functionT:QB!Q.IfTis a total function,Ais moreover calledcomplete. Automata with outputgeneralize the concept of automaton. Instead of a set Fof nal states, they have anoutput functionlabelling each state by a letter of some alphabetA. For classical automata,A=f0;1g, and a state is labelled by 1 if it is nal; otherwise it is labelled by 0. An automaton with outputcomputesa relationRB Ain the following way : (w;a)isinRif and only if there is a path labelled bywfrom some initial state to some state whose output isa.Any complete deterministic automaton with output computes a functions:B !A. Several proofs in this paper use well-known properties of automata and recogniz- able sets, for instance the equivalence between automata and complete deterministic automata, the closure under Boolean operations of the family of recognizable sets, and the equivalence between automata reading words from left to right and those reading them from right to left. In particular, we frequently use properties of right-congruences associated with recognizable sets. LetLB ; recall that the following relation L overB u L v,[8w2B ;uw2L,vw2L] is aright-congruence, i.e., an equivalence relation which isright-stable: u L v)uw L vw :

SetLis the union of some equivalence classes of

L .Moreover,Lis recognizable if and only if L has nite index. All these porperties are known as the Myhill-Nerode theorem.

Theminimal automatonA(L) of a recognizable setLB

is the smallest (in number of states) complete deterministic automaton computing it. It is unique up to isomorphism and can be constructed in the following way. Its states are the classes of L , the initial state is the class of the empty word and the nal states are the classes containing the words ofL. A transition labelled byb2Bgoes from the class ofwto the class ofwb.

194V. Bruyere - G. Hansel - C. Michaux - R. Villemaire

The automatonA(L) has two nice properties. For any pair of distinct states q;q 0 , there existsw2B such thatT(q;w) is nal andT(q 0 ;w)isnot,orviceversa.

Any classCof

L is a state ofA(L), but it is also the set of words labelling paths from the initial state to stateC.

As usual, therationaloperations are[;and

. They operate on sets of words L;L 0 B ,L[L 0 is their union,LL 0 =fww 0 jw2L;w 0 2L 0 gtheir concatenation andL the submonoid ofB generated byL.ThesetLB is then said to be rationalif it can be constructed from nite subsets ofB using a nite number of rational operations.Kleene's theoremstates thatLB is rational if and only if it is recognizable. The setN=f0;1;2;:::gis also a monoid, with operation + and neutral element

0. The same holds forN

m ;m>2, with the vectorial sum + and neutral element0.

We use the notation

nfor them-tuple (n 1 ;:::;n m ). Rational operations and rational subsets can also be dened in these monoids. InN m , the rational operations[, and are interpretedas the operations[;+ and the closure under addition (L is the submonoid ofN m generated byL). On the other hand, the notion of recognizable set is extended toN m using the right-congruence dened above :LN m is said to berecognizableif the right-congruence L has nite index. Kleene's theorem holds inNwhich is the free monoid generated by 1, but it is no longer true inN m ;m>2. Indeed, any recognizable subset is rational, but the converse is false. For instance thediagonalL=f(n;n)jn2Ngis the rational set (1;1) ofN 2 but it is not recognizable (since any two points (n;0) and (m;0) withn6=mare not equivalent for L ) (see for example [58, page 16]).

3 Some Notions of Logic

In this section, we give a short lesson in rst-order logic. The reader is referred to [3] for more details about rst-order logic.

3.1 Structures and Formulae

In the sequel, we will often meet the structureshN;+iandhN;+;V p i. In rst-order logic, astructure

S=hD;(R

i i2I ;(f j j2J ;(c k k2K i consists of adomainD(some set), a family ofrelations(R i i2I onD, a family of functions(f j j2J onDand a family ofconstants(c k k2K ofD. The relationR i is a subset ofD n i andf j is a function fromD n j toD.Thesetf(R i i2I ;(f j j2J ;(c k k2K g is called thelanguageof the structureS. For instance, the structurehN;+ihas the setNof natural numbers as domain and the usual function +. It has no relation and no constant. First-order formulaeof the structureS(or in the language ofS) are constructed by certain rules. But rst we need to list thesymbolsused in the formulae and to dene theterms.

In addition to the symbols of relationsR

i , functionsf j and constantsc k ,there are also a countable set ofvariablesx;y;z;:::, the usualconnectives_(or),^(and),

Logic andp-recognizable sets of integers195

:(not),!(if then),$(if and only if), thequantiers8(for all),9(there exists) and the symbol = (equal). Thetermsare dened by induction following two rules :

1. any variable and constant is a term,

2. iff

j is an-ary function andt 1 ;:::;t n are terms, thenf j (t 1 ;:::;t n ) is a term.

Theformulaeare generated by four rules :

1. ift

1 ;t 2 are terms, thent 1 =t 2 is a formula,

2. ifR

i is an-ary relation andt 1 ;:::;t n are terms, thenR i (t 1 ;:::;t n )isaformula,

3. if';are formulae, then'_;'^;:';'!;'$are formulae,

4. if'is a formula andxis a variable, then8x';9x'are formulae.

For clarity, parentheses (;) are necessary during the construction of formulae. For- mulae generated only by the rst two rules are calledatomic formulae.Sentences are formulae with nofreevariables, i.e., variables which are not under the scope of a quantier. We sometimes write'(x 1 ;:::;x n ) to explicitlymention the free variables of the formula'. We point out that the presentation is here a bit dierent from the one usually given in logic textbooks.

3.2 Examples

The formula

(9z)(x+z=y) of the structurehN;+imeans \there existsz2Nsuch thatx+z=y"; hence it denes the relationx6y. The constantx= 0 can also be dened inhN;+iby the formula \x6yfor ally2N", i.e. (8y)(x6y) wherex6yis the formula above. More generally, any element ofNcan be dened in the language ofhN;+i.Forx= 1, it is the following formula (:(x=0))^((8y)(:(y=0))!(x6y)): which means thatxis not 0 andx6yfor anyy2Nnf0g.Weusex=0asa short-hand for the formula (8y)(x6y) dening it. It is also easy to see that the multiplication by a constant can be dened in hN;+i. Multiplication ofxby 3,y=3x, is simply the formulay=x+x+x. Finally, the property of commutativity of addition is described by the sentence (8x)(8y)(x+y=y+x):

196V. Bruyere - G. Hansel - C. Michaux - R. Villemaire

3.3 Denable Sets and Functions

Let'(x

1 ;:::;x n ) be a formula of the structureSandd 1 ;:::;d n elements of the domainD.Weusethenotation

Sj='(d

1 ;:::;d n to state that'(x 1 ;:::;x n ) is true when the free variablesx i are replaced by the elementsd i ofD,16i6n. Therefore f(d 1 ;:::;d n )2D n jSj='(d 1 ;:::;d n )g is the set ofn-tuples of elements ofDfor which'is true. We say that this set is rst-order denable(or in shortdenable) in the structureSby the formula'. We say that a constantcisdenablein the structureSif the singletonfcgis denable inS. A relationRisdenableinSif the subset associated withRis denable inS. In the same way, we say that a functionf:D n !Disdenablein the structureSif itsgraph f(d 1 ;:::;d n ;d)2D n+1 jf(d 1 ;:::;d n )=dg is denable inS.

In this paper, we mainly study sequences (s

n n>0 and more generally multi- dimensional sequences, whose values belong to a nite subsetAofN. These se- quences are simply functionss:N m !A;m>1. Thus, we can speak ofrst-order denablesequences.

For instance the sequences:N!Adened bys

n =nmod 3 is denable in the structurehN;+i. Indeed,s 1 (0) is the set of multiples of 3 which is dened by the formula' 0 (x) (9z)(x=3z):

The sets

1 (1) is dened by' 1 (x)equalto(9z)(x=3z+1),ands 1 (2) by' 2 (x) equal to (9z)(x=3z+2). Therefore, the sequences:N!f0;1;2g,orequivalently its graph, is rst-order denable by the following formula'(x;y) 0 (x)^y=0)_(' 1 (x)^y=1)_(' 2 (x)^y=2):

This example also shows that a sequences:N

m !A,withAa nite subset of

N, is denable if and only if all the setss

1 (a);a2A, are denable.

3.4 Equivalent Structures

Consider two structuresS;S

quotesdbs_dbs47.pdfusesText_47

[PDF] MATHS lvl 4eme

[PDF] maths méthode singapour ce1

[PDF] Maths mini questions

[PDF] maths modernes et canard enchainé

[PDF] maths montrer que

[PDF] maths mpsi ellipses pdf

[PDF] maths mpsi exercices corrigés

[PDF] maths mpsi exercices corrigés pdf

[PDF] maths niveau 3eme

[PDF] maths niveau 5eme

[PDF] maths niveau seconde dm

[PDF] Maths nombres relatifs

[PDF] Maths nombres relatifs et possitives

[PDF] Maths Noté exercices

[PDF] Maths Numerique