Abstracts Computer Science

Logical Aspects of Regular Languages

by Boris Dashkovsky

A thorough review of selected results on the logical aspects of regular languages includes the theorem of Büchi on monadic second order logic over strings, a characterization of FO[<l and the theorem of 1. Simon. With the help of the Ehrenfeucht-Fraïssé Game we show that :J(k+ltsentences of FO[<1 cannot be expressed as a boolean combination of :J(ktsentences. Block product of finite monoids is used to analyze languages defined by the boolean closure of the 2::2-sentences. Positive varieties and the Mal'cev product are introduced and 2::n +l n IIn+l is shown to be equal to the unambiguous polynomial closure of the nth level of the Straubing-Thérien hierarchy. In particular, 2:: 2 n II2 = VA, where VA is the smallest variety of languages closed under the unambiguous product. Nous proposons un aperçu complet de résultats choisis concernant les aspects logiques des langages réguliers incluant le théorème de Büchi sur la logique monadique de second ordre sur les chaînes de caractères, la caractérisation de FO[<J et le théorème de 1. Simon. Grâce au jeu de Ehrenfeucht-Fraïssé, nous démontrons que, dans FO[<J, les énoncés logiques 3(k+1) ne peuvent être exprimés comme une combinaison booléene d'énoncés 3(k). Nous utilisons le produit bloc de monoïdes finis pour analyser les langages définis par la fermeture booléene des énoncés 2:: 2 • Nous présentons également les variétés positives et le produit de Mal'cev et montrons que 2::n +1 n IIn+1 est égal à la fermeture polynomiale non-ambigue du nième niveau de la hiérarchie de StraubingThérien. En particulier, 2:: 2 n II2 = VA, où VA est la plus petite variété de langages fermée sous le produit non-ambigu fr