A duality theoretic perspective on recognisable languages

Journal Title
Journal ISSN
Volume Title
Stellenbosch : Stellenbosch University
ENGLISH ABSTRACT : A connection between recognisable languages and profinite identities is established through the composition of two famous theorems: Eilenberg’s theorem and Reiterman’s theorem. In this work, we present a detailed account of the duality-theoretic approach by Gehrke et al. that has been shown to bridge the gap and demonstrate that Eilenberg’s varieties and profinite theories are directly linked: they are at opposite ends of an extended Stone-type duality, instantiating a Galois correspondence between subobjects and quotients and resulting in an equational theory of recognisable languages. We give an indepth overview of relevant components of algebraic language theory and the profinite equational theory of pseudovarieties in order to show how they are tied together by the duality-theoretic developments. Furthermore, we provide independent proofs of the key Galois connections at the heart of these bridging results.
AFRIKAANSE OPSOMMING : Geen Afrikaanse opsomming geskikbaar nie
Thesis (MSc)--Stellenbosch University, 2019.
Boolean algebras, Formal language theory, Duality theory (Mathematics), Lattices, Stone duality (Mathematics), UCTD