Topological Algebras On Boolean Spaces As Dual Spaces And .

Topological algebras on Boolean spacesas dual spacesandapplications in formal language theoryMai GehrkeCNRS and Paris Diderot

Stone dualityDL0-dimCompHausBAdualequivalenceSpectral spacesStably compact spacesProximity latticesSpatial framesA B quotientA - B subalgebraA B coproductA B productf : An A operation Jonsson-Tarski 1951 for BAOsSober spacesXXXXR - Y subspace Y quotient space Y product · Y sum X X n dual relation

ntaxand theorysemanticsDualityin semantics IDeductive! systems!"!""!"Abstract ! Algebras S#ClopenTopo-RelationalStructures!βδ"Concrete Algebras AtP#"Relational ! Structures!"!"!""!"Relational Semantics

Duality theory in semantics IIIλ-calculus (a functional calculus allowing self application)λx.xxsemantics? Scott’s modelScott’s models are Stone dual spacesApplication for a DR positionIDomain theory(M, N) : σ τM : σ, N : τprogram logicfor program specificationsemantics? (Domains in logical form - Abramsky)domain Abramsky: Domains are obtainable as dual spaces of programlogics

Duality theory in logic and computer scienceDuality theory has been very successful in semantics. It often playsa role in:ICompleteness: Duality helps in obtaining semanticsIDecidability: Sometimes the dual of a problem is easier tosolve.So far, there have been very few applications of duality theory incomplexity theory

Duality theory in complexity theoryIn complexity theory computing machines are studied, e.g.,through corresponding formal languagesTypical problems are decidability, separation, and comparison ofcomplexity classesIn joint work with Serge Grigorieff and Jean-Eric Pin we haveshown that duality theory is responsible for the standard tool forproving decidability results in automata theory

A finite automatona12bba3a, bThe states are {1, 2, 3}.The initial state is 1, the final states are 1 and 2.The alphabet is A {a, b} The transitions are1·a 21·b 32·a 32·b 13·a 33·b 3

Recognition by automataa12bba3a, bTransitions extend to words: 1 · aba 2, 1 · abb 3.The language recognized by the automaton is the set of words usuch that 1 · u is a final state. Here:L(A) (ab) (ab) awhere means arbitrary iteration of the product.

Rational and recognizable languagesA language is recognizable provided it is recognized by some finiteautomaton.A language is rational provided it belongs to the smallest class oflanguages containing the finite languages which is closed underunion, product and star.Theorem: [Kleene ’54] A language is rational iff it is recognizable.Example:L(A) (ab) (ab) a.

Logic on wordsTo each non-empty word u is associated a structureMu ({1, 2, . . . , u }, , (a)a A )where a is interpreted as the set of integers i such that the i-thletter of u is an a, and as the usual order on integers.Example:Let u abbaab thenMu ({1, 2, 3, 4, 5, 6}, , (a, b))where a {1, 4, 5} and b {2, 3, 6}.

Some examplesThe formula φ x ax interprets as:There exists a position x in u such thatthe letter in position x is an a.This defines the language L(φ) A aA .The formula x y (x y ) ax by defines the languageA aA bA .The formula x y [(x y ) (x y )] ax defines the languageaA .

Defining the set of words of even lengthMacros:(x y ) (x y ) means x 6 y y x 6 y means x 1 y y 6 x means x u x y z (x z y 6 z) means y x 1Let φ X (1 / X u X x (x X x 1 / X ))Then 1 / X, 2 X, 3 / X , 4 X , . . . , u X . ThusL(φ) {u u is even} (A2 )

Monadic second orderOnly second order quantifiers over unary predicates are allowed.Theorem: (Büchi ’60, Elgot ’61)Monadic second order captures exactly the recognizable languages.Theorem: (McNaughton-Papert ’71)First order captures star free languages(star free the ones that can be obtained from the alphabet usingthe Boolean operations on languages and lifted concatenationproduct only).How does one decide the complexity of a given language?

Algebraic theory of automataTheorem: [Myhill ’53, Rabin-Scott ’59] There is an effective way ofassociating with each finite automaton, A, a finite monoid,(MA , ·, 1).Theorem: [Schützenberger ’65] Star free languages correspond toaperiodic monoids, i.e., M such that there exists n 0 withx n x n 1 for each x M.Submonoid generated by x:x i 11xx2x3x i p x i.This makes star freeness decidable!x i p 1x i 2

An exampleL (ab) M(L) ·1ababab01 a ba b ab 01 a ba b ab 0a 0 a ab 0 0ba 0 ba b 0 0b ba b 0 b 0ab a 0 0 ab 00 0 0 0 0 0Syntactic monoidThis monoid is aperiodic since 1 12 , a2 0 a3 , ba ba2 ,b 2 0 b 3 , ab ab 2 , and 0 02Indeed, L is star-free since Lc bA A a A aaA A bbA andA c

Eilenberg-Reiterman theoryVarieties offinite monoidsEilenbergVarietiesof languagesReitermanProfiniteidentitiesIn goodcasesDecidabilityA variety of monoids here means a class of finite monoids closedunder homomorphic images, submonoids, and finite productsVarious generalisations: [Pin 1995], [Pin-Weil 1996], [Pippenger1997], [Polák 2001], [Esik 2002], [Straubing 2002], [Kunc 2003]

Eilenberg, Reiterman, and StoneClasses of monoids(1)(2)algebras of languagesequational theories(3)(1) Eilenberg theorems(2) Reiterman theorems(3) extended Stone/Priestley duality(3) allows generalisation to non-varieties and even to non-regularlanguages

Connection between duality and Eilenberg-Reiterman IIIIThe syntactic monoid of a language L is the dual of a certainBAO generated by L in P(A )c , the dual of Rec(A ) equippedThe free profinite monoid, Awith certain residuation operationsSublattices of Rec(A ) correspond via duality to quotients ofc Ac )c (and hence equations/pairs in AA

Connection between duality and Eilenberg-Reiterman IIIThe dual of a continuous operation·:X X Xshould be a coalgebraic structureh :A A A(this is the approach in classical algebra; see also Steinbergand Rhodes)IIt turns out that in an order theoretic setting, the residuals ofthe product encode this algebra giving and algebraic dual to atopological algebraIFrom a lattices and order point of view, residuals aregeneralised implications, and the pertinent structures areclosely related to nuclei.

The residuals of the concatenation productaConsider a finite state automaton12bba3a, bThe language recognized by A is L(A) (ab) (ab) aQuotient operations on languages:a 1 L {u A au L} (ba) b (ba) La 1 {u A ua L} (ab) b 1 L {u A bu L} All recognised by the same underlying machine!

Capturing the underlying machineGiven a recognizable language L the underlying machine iscaptured by the Boolean algebra B(L) of languages generated by x 1 Ly 1 x, y A NB! This generating set is finite since all the languages arerecognized by the same machine with varying sets of initial andfinal states.NB! B(L) is closed under quotients since the quotient operationscommute will all the Boolean operations.

The residuation ideal generated by a languageSince B(L) is finite it is also closed under residuation. That is, forM B(L)S\M \u SM/S \u Su 1 M B(L)Mu 1 B(L)These are the upper adjoints in the left and right coordinate of thelifted product on P(A )KL M L K \M K M/L(B(L), \, /) is a Boolean Algebra with additional Operations (BAO)

The syntactic monoid of a recognizable language[G-Grigorieff-Pin 2008]The relation dual to \ and / on B(L) is a functionf :X X XTheorem: The dual space of the BAO (B(L(A)), \, /) is thesyntactic monoid of L(A)

Boolean topological algebrasWe call a topological algebra of some algebraic type τ Booleanprovided the underlying topological space is BooleanTheorem: Let X be a Boolean space, f : X n X any function,and R X n X its graph. The the following are equivalent:IR is a dual relation with i as the output coordinate for some(and then for all) 1 6 i 6 nIf is continuousCorollary: All Boolean topological algebras are dual spaces ofcertain residuation algebras (as are all Priestley topologicalalgebras)

Duals of topological algebra morphisms.are different (and incomparable) to residuation algebramorphisms in generalA special well behaved case: the dual of a Boolean topologicalalgebra quotient is a Boolean residuation ideal:C , B Boolean residuation subalgebra with b\c and c/b C forall b B and c C

Characterization of profinite algebrasThe inverse limit system Flim F X XkXjXiAll the Xi ’s are finite topological algebra quotients, so by dualitythe dual Boolean residuation algebra is a directed union of finiteBoolean residuation idealsTheorem: A Boolean topological algebra X is profinite iff eachfinitely generated Boolean residuation ideal of the dual algebra isfinite

Profinite completionsAThe inverse limit system FA!lim FA A HFGis dual toP(A)lim GA Rec(A) The direct limit system GAP(H)P(G )P(F )[lim GA {ϕ 1 (P(F )) ϕ : A F finite quotient} {ϕ 1 (P) ϕ : A F finite quotient and P F } Rec(A)

Profinite completionsTheorem: [G-Grigorieff-Pin 2008] The profinite completion of ANYalgebra is the dual space of the BAO Rec(A) with the residuals ofthe lifted operations

Eilenberg-Reiterman theoryVarieties offinite monoidsEilenbergVarietiesof languages[Eilenberg76] [Reiterman82]ReitermanProfiniteidentitiesIn goodcasesDecidability

Characterizing subclasses of languages[G-Grigorieff-Pin 2008] subalgebrasquotient structuresC a class of recognizable languages closed under and C, Rec(A )DUALLYXC c Ac .That is, C is described dually by EQUATING elements of AThis is a general form of Eilenberg-Reiterman theorem

A Galois connection for subsets of an algebraLet B be a Boolean algebra, X the dual space of B.The maps P(B) P(X X ) given byS 7 S {(x, y ) X b S(b y b x)}E 7 BE {b B (x, y ) E(b y b x)}andestablish a Galois connection whose Galois closed sets are theBoolean equivalence relations and the Boolean subalgebras,respectively.

Example[Schützenberger 1965]Star-free languages 6 Rec(A )c dual to this residuation ideal isThe equivalence relation on Agenerated in the Galois connection of the previous slide by the setc }{(ux ω 1 v , ux ω v ) x, u, v AThat is, it is given by ONE pair, (aω 1 , aω ), when closing under:IsubstitutionImonoid congruenceIStone duality subalgebra-quotient adjunction

ReferencesThe following are the papers from which the research discussed atthe two talks I gave at AAA88 came:1. Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin, Duality andEquational Theory of Regular Languages, LNCS (ICALP)5125 (2008), 246–257.2. Mai Gehrke, Stone duality, topological algebra, andrecognition, preprint. See,http://hal.archives-ouvertes.fr/hal-008597173. Mai Gehrke, Andreas Krebs, and Jean-Éric Pin, Fromultrafilters on words to the expressive power of a fragment oflogic, to appear in Proceedings of the 16th InternationalWorkshop on Descriptional Complexity of Formal Systems,2014.

Boolean topological algebras We call a topological algebra of some algebraic type Boolean provided the underlying topological space is Boolean Theorem: Let X be a Boolean space, f : Xn!X any function, and R Xn X its graph. The the following are equivalent: IR is a dual relation with i as the output coordinate for some (and then for all) 1 6i 6n