A duality theoretic perspective on recognisable languages

Rozanova, Julia (2019-04)

Thesis (MSc)--Stellenbosch University, 2019.


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

Please refer to this item in SUNScholar by using the following persistent URL: http://hdl.handle.net/10019.1/105807
This item appears in the following collections: