[PDF] Mathematical Foundations of Automata Theory

View - Download Mathematical Foundations of Automata Theory

Previous PDF

Next PDF

Mathematical Foundations

of Automata Theory Jean-

´Eric Pin

Version of February 18, 2022

PrefaceThese notes form the core of a future book on the algebraic foundations of automata theory. This book is still incomplete, but the firsteleven chapters now form a relatively coherent material, covering roughly the topics described below.

The early years of automata theory

Kleene"s theorem [

68] is usually considered as the starting point of automata

theory. It shows that the class of recognisable languages (that is, recognised by finite automata), coincides with the class of rational languages, which are given by rational expressions. Rational expressions can bethought of as a generalisation of polynomials involving three operations: union (which plays the role of addition), product and the star operation. It was quickly observed that these essentially combinatorial definitions can be interpreted in a very rich way in algebraic and logical terms. Automata over infinite wordswere introduced by B¨uchi in the early 1960"s to solve decidability questions in first-order and monadic second-order logic of one successor. Investigating two-successor logic, Rabin was led to the concept of tree automata, which soon became a standard tool for studying logical definability.

The algebraic approach

The definition of thesyntactic monoid, a monoid canonically attached to each language, was first given by Sch¨utzenberger in 1956 [

138]. It later appeared in

a paper of Rabin and Scott [

129], where the notion is credited to Myhill. It

was shown in particular that a language is recognisable if and only if its syn- tactic monoid is finite. However, the first classification results on recognisable languages were rather stated in terms of automata [

89] and the first nontrivial

use of the syntactic monoid is due to Sch¨utzenberger [

139]. Sch¨utzenberger"s

theorem (1965) states that a rational language is star-freeif and only if its syn- tactic monoid is finite and aperiodic. This elegant result isconsidered, right after Kleene"s theorem, as the most important result of the algebraic theory of automata. Sch¨utzenberger"s theorem was supplemented a few years later by a result of McNaughton [

84], which establishes a link between star-free languages

and first-order logic of the order relation. Both results had a considerable influence on the theory. Two other important algebraic characterisations date back to the early seventies: Simon [

142] proved

that a rational language is piecewise testable if and only ifits syntactic monoid isJ-trivial and Brzozowski-Simon [

23] and independently, McNaughton [83]

3

4characterised the locally testable languages. The logicalcounterpart of the first

result was obtained by Thomas [

164]. These successes settled the power of the

algebraic approach, which was axiomatized by Eilenberg in 1976 [ 42].

Eilenberg"s variety theory

A variety of finite monoids is a class of monoids closed under taking submonoids, quotients and finite direct products. Eilenberg"s theorem states that varieties of finite monoids are in one-to-one correspondence with certain classes of recognis- able languages, the varieties of languages. For instance, the rational languages are associated with the variety of all finite monoids, the star-free languages with the variety of finite aperiodic monoids, and the piecewise testable languages with the variety of finiteJ-trivial monoids. Numerous similar results have been es- tablished over the past thirty years and, for this reason, the theory of finite automata is now intimately related to the theory of finite monoids. Several attempts were made to extend Eilenberg"s variety theory to a larger scope. For instance, partial order on syntactic semigroupswere introduced in

99], leading to the notion of ordered syntactic semigroups. The resulting exten-

sion of Eilenberg"s variety theory permits one to treat classes of languages that are not necessarily closed under complement, contrary to the original theory. Other extensions were developed independently by Straubing [

158] and´Esik and

Ito [ 45].

The topological point of view

Due allowance being made, the introduction of topology in automata theory can be compared to the use ofp-adic analysis in number theory. The notion of a variety of finite monoids was coined after a similar notion, introduced much earlier by Birkhoff for infinite monoids: aBirkhoff variety of monoidsis a class of monoids closed under taking submonoids, quotient monoids and direct products. Birkhoff proved in [

15] that his varieties can be defined by

a set of identities: for instance the identityxy=yxcharacterises the variety of commutative monoids. Almost fifty years later, Reiterman[

131] extended

Birkhoff"s theorem to varieties of finite monoids: any variety of finite monoids can be characterised by a set ofprofinite identities. A profinite identity is an identity between two profinite words. Profinite words can be viewed as limits of sequences of words for a certain metric, the profinite metric. For instance, one can show that the sequencexn!converges to a profinite word denoted by x ωand the variety of finite aperiodic monoids can be defined by the identity x

ω=xω+1.

The profinite approach is not only a powerful tool for studying varieties but it also led to unexpected developments, which are at the heart of the current research in this domain. In particular, Gehrke, Grigorieff and the author [ 47]
proved that any lattice of recognisable languages can be defined by a set of profinite equations, a result that subsumes Eilenberg"s variety theorem.

The logical approach

We already mentioned B¨uchi"s, Rabin"s and McNaughton"s remarkable results on the connection between logic and finite automata. B¨uchi"ssequential calculus 5 is a logical language to express combinatorial properties of words in a natural way. For instance, properties like "a word contains two consecutive occurrences ofa" or "a word of even length" can be expressed in this logic. However, several parameters can be adjusted. Different fragments of logic canbe considered: first-order, monadic second-order, Σquotesdbs_dbs2.pdfusesText_3

[PDF] theory of quadratic equation

[PDF] theory of semiotics ferdinand de saussure pdf

[PDF] therapeutic drug monitoring pdf

[PDF] therapeutic drug monitoring ppt

[PDF] therapeutic drug monitoring principles

[PDF] therapeutic drug monitoring review

[PDF] thermal model of a house

[PDF] thermostat simulink

[PDF] thesis about british and american english

[PDF] thesis on android application development

[PDF] thesis outline example

[PDF] thirty years war essay question

[PDF] thirty years war essay thesis

[PDF] thirty years war political causes

[PDF] thirty years' war