Return to search

Counting subwords and other results related to the generalised star-height problem for regular languages

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.

Identiferoai:union.ndltd.org:bl.uk/oai:ethos.bl.uk:730714
Date January 2017
CreatorsBourne, Thomas
ContributorsRuskuc, Nik ; Roney-Dougal, Colva Mary
PublisherUniversity of St Andrews
Source SetsEthos UK
Detected LanguageEnglish
TypeElectronic Thesis or Dissertation
Sourcehttp://hdl.handle.net/10023/12024

Page generated in 0.0023 seconds