O identitetima algebri regularnih jezika

Abstract

Jezik nad E je proizvoljan skup reci nad E, tj. proizvoljan podskup slobodnog monoida E*. Jezici nad datom azbukom formiraju al­ gebre jezika, sa operacijama unije, konkatenacije (dopisivanja red), Kleene-jeve iteracije i sa 0, {A} kao konstantama. Regularni jezici nad E su elementi podalgebre algebre jezika nad E generisane konačnim jezicima. Ispostavlja se da algebre jezika generišu isti varijetet (i stoga zadovoljavaju iste iden­titete) kao i algebre binarnih relacija snabdevene operacijama unije, kompozi­cije, refleksivno-tranzitivnog zatvorenja i praznom relacijom i dijagonalom kao konstantama. Reč je o varijetetu Kleenejevih algebri, i slobodne algebre tog varijeteta su baš algebre regularnih jezika. Na početku disertacije, izloženi su neki aspekti algebarske teorije automata i formalnih jezika, teorije binarnih relacija i univerzalne algebre, relevantni za ispitivanje identiteta na algebrama jezika. Zatim je dat klasični rezultat (Redko, 1964.) da varijetet Kleenejevih algebri nema konačnu bazu identiteta. Ovde je prikazan dokaz Conwaya iz 1971., budući da on sadrži neke ideje koje su se pokazale korisne za dalji rad. Glave 3 i 4 sadrže originalne rezultate usmerene na profinjenje Redkovog rezultata. Pokazano je da uzroci beskonačnosti baze identiteta za Kleenejeve algebre leže u interakciji operacija konkatenacije i iteracije jezika (odnosno, kompozicije i refleksivno-tranzitivnog zatvorenja relacija). Drugim recima, klasa redukata algebri jezika bez operacije unije nema konačnu bazu identiteta. To daje odgovor na problem D. A. Bredikhina iz 1993. godine. S druge strane, proširenjem tipa Kleenejevih algebri involutivnom operacijom inverza jezika, odnosno relacija, takođe se dolazi do beskonačno baziranih varijeteta, čime se rešava problem B. Jonssona iz 1988. godine. Analogno, komutativni jezici nad E su proizvoljni podskupovi slobodnog komutativnog monoida E®. U Glavi 5 je dokazano da se jednakosna teorija algebri komutativnih jezika poklapa sa jednakosnom teorijom algebre (regu­larnih) jezika nad jednoelementnim alfabetom, što daje odgovor na problem koji je još 1969. formulisao A. Salomaa u svojoj monografiji Theory of Au­tomata.Na taj način, iz poznatih rezultata o jednakosnoj aksiomatizaciji komutativnih jezika se dobija jedna baza za algebre jezika nad jednoelement­nim alfabetom, kao i veoma kratak dokaz poznate činjenice (takođe Redko, 1964.) da algebre komutativnih jezika nemaju konačnu bazu identiteta. Na kraju disertacije, identiteti Kleenejevih algebri se posmatraju u kon­tekstu dinamičkih algebri. Reč je o algebarskoj verziji dinamičkih logika, koje su konstruisane sedamdesetih godina kao matematički model rada računara, kada se na njima izvršava program pisan u nekom imperativnom program­ skom jeziku. Na primer, problemi verifikacije i ekvivalentnosti programa se lako izražavaju preko identiteta dinamičkih algebri, tako da razne njihove jednakosne osobine odgovaraju pojmovima iz teorijskog računarstva. Takođe, interesatno je da je jednakosna teorija Kleenejevih algebri ’’ kodirana” u konačno baziranoj jednakosnoj teoriji dinamičih algebri. Polazeći od poznatih rezul­tata za dvosortne dinamičke algebre (pri čemu je jedna komponenta algebra istog tipa kao i Kleenejeve algebre, dok je druga Booleova algebra), neki od tih rezultata su transformisani i prošireni za Jonssonove dinamičke algebre (jednosortne modele dinamičkih logika). Na primer, ako se Kleenejeva algebra K može predstaviti kao konačan direktan proizvod slobodnih algebri varijeteta Kleenejevih algebri generisanih Kleenejevim relacionim algebrama, tada vari­jetet K-dinamičkih algebri ima odlučivu jednakosnu teoriju. Odavde se izvodi da svaki varijetet Kleenejevih algebri generisan Kleenejevim relacionim algeb­rama takođe ima odlučivu jednakosnu teoriju.

A language over £ is an arbitrary set of words, i.e. any subset of the free monoid £*. All languages over a given alphabet form the algebra of languages, which is equipped with the operations of union, concate­nation, Kleene iteration and 0, {A } as constants. Regular languages over £ are the elements of the subalgebra of the algebra of languages over £ generated by finite languages. It turns out that algebras of languages generate exactly the same variety as algebras of binary relations, endowed with union, rela­tion composition, formation of the refelxive-transitive closure and the empty relation and the diagonal as constants. The variety in question is the vari­ety of Kleene algebras, and the algebras of regular languages are just its free algebras. The present dissertation starts with several aspects of algebraic theory of automata and formal languages, theory of binary relations and universal alge­bra, which are related to problems concerning identities of language algebras. This material is followed by the classical result (Redko, 1964) claiming that the variety of Kleene algebras have no finite equational base. We present the proof of Conway from 1971, since it contains some ideas which can be used for generalizations in different directions. Chapters 3 and 4 contain original results which refine the one of Redko. It is shown that the cause of nonfinite axiomatizability of Kleene algebras lies in the superposition of the concatenation and the iteration of languages, that is, composition of relations and reflexive-transitive closure. In other words, the class of -(--free reducts of algebras of languages has no finite equational base, which answers in the negative a problem of D. A. Bredikhin from 1993. On the other hand, by extending the type of Kleene algebras by the involutive operation of inverse of languages (converse of relations), we also obtain a nonfinitely based variety, which solves a problem of B. Jonsson from 1988. Analogously, commutative languages over E are defined as subsets of the free commutative monoid £®. It is proved in Chapter 5 that equational the­ ories of algebras of commutative languages and, respectively, of the algebra of (regular) languages over the one-element alphabet, coincide. This result settles a thirty year old problem of A. Salomaa, formulated back in his wellknown monograph Theory of Automata.Thus, we obtain an equational base for the algebra of one-letter languages, and, on the other hand, a very short proof of another Redko’s result from 1964, according to which there is no finite equational base for algebras of commutative languages. Finally, identities of Kleene algebras are considered in the context of dy­namic algebras, which are just algebraic counterparts of dynamic logics. They were discovered in the seventies as a result of the quest for an appropriate logic for reasoning about computer programs written in an imperative pro­ gramming language. For example, problems concerning program verification and equivalence can be easily translated into identities of dynamic algebras, so that many of their equational properties correspond to notions from computer science. It is also interesting that the whole equational theory of Kleene alge­ bras is ’’encoded” in the finitely based equational theory of dynamic algebras. Starting with known results on two-sorted dynamic algebras (where one com­ ponent is an algebra of the same signature as Kleene algebras, while the other is a Boolean algebra), some of those results are transformed and extended for Jonsson dynamic algebras (that is, one-sorted models of dynamic logics). For example, if a Kleene algebra K can be represented as a finite direct product of free algebras of varieties of Kleene algebras generated by Kleene relation algebras, then the variety of K-dynamic algebras has a decidable equational theory. The latter yields that all varieties of Kleene algebras generated by Kleene relation algebras have decidable equational theories, too.