The Generalised Star-Height Problem is an open question in the field of formal language theory that concerns a measure of complexity on the class of regular languages; specifically, it asks whether or not there exists an algorithm to determine the generalised star-height of a given regular language. Rather surprisingly, it is not yet known whether there exists a regular language of generalised star-height greater than one. Motivated by a theorem of Thérien, we first take a combinatorial approach to the problem and consider the languages in which every word features a fixed contiguous subword an exact number of times. We show that these languages are all of generalised star-height zero. Similarly, we consider the languages in which every word features a fixed contiguous subword a prescribed number of times modulo a fixed number and show that these languages are all of generalised star-height at most one. Using these combinatorial results, we initiate work on identifying the generalised star-height of the languages that are recognised by finite semigroups. To do this, we establish the generalised star-height of languages recognised by Rees zero-matrix semigroups over nilpotent groups of classes zero and one before considering Rees zero-matrix semigroups over monogenic semigroups. Finally, we explore the generalised star-height of languages recognised by finite groups of a given order. We do this through the use of finite state automata and 'count arrows' to examine semidirect products of the form A x Zr where A is an abelian group and Zr is the cyclic group of order r.
| Identifer | oai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:730714 |
| Date | January 2017 |
| Creators | Bourne, Thomas |
| Contributors | Ruskuc, Nik ; Roney-Dougal, Colva Mary |
| Publisher | University of St Andrews |
| Source Sets | Ethos UK |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Source | http://hdl.handle.net/10023/12024 |
Page generated in 0.0021 seconds