The central notionof thisthesisis repetitionsin words. We studyproblemsrelated to contiguous repetitions. More specifically we will consider repeating scattered subwords of non-primitive words, i.e. words which are complete repetitions of other words. We will present inequalities concerning these occurrences as well as giving apartial solutionto an openproblemposedby Salomaaet al. We will characterize languages, whichare closed under the operation ofduplication, thatis repeating any factor of a word. We alsogive newbounds onthe number of occurrencesof certain types of repetitions of words. We give a solution to an open problem posed by Calbrix and Nivat concerning regular languages consisting of non-primitive words. We alsopresentsomeresultsregarding theduplication closureoflanguages,among which a new proof to a problem of Bovet and Varricchio.

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.

Forbidding and enforcing systems (fe-systems) provide a new way of defining classes of structures based on boundary conditions. Forbidding and enforcing systems on formal languages were inspired by molecular reactions and DNA computing. Initially, they were used to define new classes of languages (fe-families) based on forbidden subwords and enforced words. This paper considers a metric on languages and proves that the metric space obtained is homeomorphic to the Cantor space. This work studies Chomsky classes of families as subspaces and shows they are neither closed nor open. The paper investigates the fe-families as subspaces and proves the necessary and sufficient conditions for the fe-families to be open. Consequently, this proves that fe-systems define classes of languages different than Chomsky hierarchy. This work shows a characterization of continuous functions through fe-systems and includes results about homomorphic images of fe-families. This paper introduces a new notion of connecting graphs and a new way to study classes of graphs. Forbidding-enforcing systems on graphs define classes of graphs based on forbidden subgraphs and enforced subgraphs. Using fe-systems, the paper characterizes known classes of graphs, such as paths, cycles, trees, complete graphs and k-regular graphs. Several normal forms for forbidding and enforced sets are stated and proved. This work introduces the notion of forbidding and enforcing to posets where fe-systems are used to define families of subsets of a given poset, which in some sense generalizes language fe-systems. Poset fe-systems are, also, used to define a single subset of elements satisfying the forbidding and enforcing constraints. The latter generalizes graph fe-systems to an extent, but defines new classes of structures based on weak enforcing. Some properties of poset fe-systems are investigated. A series of normal forms for forbidding and enforcing sets is presented. This work ends with examples illustrating the computational potential of fe-systems. The process of cutting DNA by an enzyme and ligating is modeled in the setting of language fe-systems. The potential for use of fe-systems in information processing is illustrated by defining the solutions to the k-colorability problem.