A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of the requirements for the degree of Master of Science. Johannesburg, October 2012. / Unable to load abstract.

The rewrite relation with parameters m and n and with the possible length limit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. The idempotency languages generated from a starting word w by the respective operations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication have come up in different contexts. The investigations of Ito et al. about insertion and deletion, Le., operations that are also observed in DNA molecules, have established that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out from the case of a uniform length bound. For these relations =kW~ the conditions for confluence are characterized completely. Also the question of regularity is -k n answered for aH the languages w- D<lm . They are nearly always regular. Only the languages wD<lo for n > 1 are more complicated and belong to the class of context-free languages.For a generallength bound, i.e."for the relations :"::kW~, confluence does not hold so frequently. This complicatedness of the relations results also in more complicated languages, which are often non-regular, as for example the languages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case of k :::; 3, though, remains open. We show, however, that none of these languages ever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicated structure. Over alphabets of one or two letters we still characterize the conditions for confluence. Over three or more letters, in contrast, only a few cases are solved. We determine the combinations of parameters that result in the regularity of wD<l::', when the alphabet of w contains only two letters. Only the case of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the special case of duplication. First we shed sorne light on the reasons why it is so difficult to determine the context-freeness ofduplication languages. We show that they fulfiH aH pumping properties and that they are very dense. Therefore aH the standard tools to prove non-context-freness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describe the reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementary in connection with duplication are square-free words, Le., words that do not contain any repetition. Thus we define the duplication root of w to consist of aH the square-free words, from which w can be reached via the relation w~.Besides sorne general observations we prove the decidability of the question, whether the duplication root of a language is finite.Then we devise acode, which is robust under duplication of its code words.This would keep the result of a computation from being destroyed by dupli cations in the code words. We determine the exact conditions, under which infinite such codes exist: over an alphabet of two letters they exist for a length bound of 2, over three letters already for a length bound of 1.Also we apply duplication to entire languages rather than to single words; then it is interesting to determine, whether regular and context-free languages are closed under this operation. We show that the regular languages are closed under uniformly bounded duplication, while they are not closed under duplication with a generallength bound. The context-free languages are closed under both operations.The thesis concludes with a list of open problems related with the thesis' topics.

In this paper, the mathematical theory of languages is used to investigate and develop computer systems for music analysis, composition, and performance. Four prominent research projects in the field are critically reviewed. An original grammar-type for the computer representation of music is introduced, and a computer system for music composition and performance based on that grammar is described. A user's manual for the system is provided as an appendix.

The notion of communication complexity was introduced by Yao in his seminal paper [Yao79]. In [BFS86], Babai Frankl and Simon developed a rich structure of communication complexity classes to understand the relationships between various models of communication complexity. This made it apparent that communication complexity was a self-contained mini-world within complexity theory. In this thesis, we study the place of regular languages within this mini-world. In particular, we are interested in the non-deterministic communication complexity of regular languages. / We show that a regular language has either O(1) or O(log n) non-deterministic complexity. We obtain several linear lower bound results which cover a wide range of regular languages having linear non-deterministic complexity. These lower bound results also imply a result in semigroup theory: we obtain sufficient conditions for not being in the positive variety Pol(Com). / To obtain our results, we use algebraic techniques. In the study of regular languages, the algebraic point of view pioneered by Eilenberg ([Eil74]) has led to many interesting results. Viewing a semigroup as a computational device that recognizes languages has proven to be prolific from both semigroup theory and formal languages perspectives. In this thesis, we provide further instances of such mutualism.

Thesis (Ph. D.)--State University of New York at Binghamton, Mathematical Sciences Department, 2007. / Includes bibliographical references.

Thesis (Ph. D.)--University of Wisconsin--Madison, 1973. / Typescript. Vita. eContent provider-neutral record in process. Description based on print version record. Includes bibliographical references.

Thesis (MSc)--University of Stellenbosch, 2008. / Bibliography. Also available via the Internet.

Thesis--University of North Carolina. / Photocopy of type-script. Bibliography: leaves [143]-146.

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2005. / Includes bibliographical references (leaves 100-106). Also available in electronic version.

A group whose co-word problem is a context free language is called coCF. Lehnert's conjecture states that a group G is coCF if and only if G embeds as a finitely generated subgroup of R. Thompson's group V. In this thesis we explore a class of groups, Faug, proposed by Berns-Zieze, Fry, Gillings, Hoganson, and Mathews to contain potential counterexamples to Lehnert's conjecture. We create infinite and finite presentations for such groups and go on to prove that a certain subclass of Faug consists of groups that do embed into V. By Anisimov a group has regular word problem if and only if it is finite. It is also known that a group G is finite if and only if there exists an embedding of G into V such that its natural action on C₂:= {0,1}^w is free on the whole space. We show that the class of groups with a context free word problem, the class of CF groups, is precisely the class of finitely generated demonstrable groups for V. A demonstrable group for V is a group G which is isomorphic to a subgroup in V whose natural action on C₂ acts freely on an open subset. Thus our result extends the correspondence between language theoretic properties of groups and dynamical properties of subgroups of V. Additionally, our result also shows that the final condition of the four known closure properties of the class of coCF groups also holds for the set of finitely generated subgroups of V.