Back to search

University of York

Recognisable languages over free algebras

Abstract

dc:description.abstract

This thesis considers notions of recognisability for languages over (universal) algebras. The main motivation here is the body of work on recognisable languages over the free monoid, which in particular connects several, equivalent, approaches. The free monoid X^* on a set X consists of all finite strings of elements of X; these are thought of as words, and hence a subset of X^* is known as a language (i.e. a collection of words). The term is then used for a subset of any (free) algebra. Our first approach to recognisability is via finite index of syntactic congruences; the latter may be defined for any kind of algebra. We consider how to define syntactic congruences in the most efficient way: absolutely, or with regard to a particular class of algebras or languages. We give examples where only finitely many terms are needed to determine syntactic congruences. For a particular class of free algebras we find an infinite list of terms, each built from the previous, and give an example of a language such that we need to check terms of every kind. Using syntactic congruences we consider closure properties of recognisable languages. We give many examples, including critical examples of languages that are themselves free algebras (in some sense) but are contained in the free inverse monoid. Our second approach is in the context of unary monoids. We introduce a new kind of formal machine we call a +-automaton. Our main result in this regard is to show that a language over a free unary monoid has syntactic congruence of finite index if and only if it is recognised by a +-automaton. This result exactly parallels the well known result for languages over free monoids.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of York
Year dc:date.issued
2021

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Cheng, Kei Tsi Daniel
Advisor dc:contributor.advisor
  • Gould, Victoria

Rights

Language dc:language.dcterms_iso639_2
eng

Identifiers

dc:identifier.*
Identifier
uk.bl.ethos.844262

Chain of custody

source
Harvested from
White Rose University Consortium
Base URL
etheses.whiterose.ac.uk/cgi/oai2
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Cheng, Kei Tsi Daniel. Recognisable languages over free algebras. doctoral thesis, University of York, 2021.