Projekt A4 - Kombinatorische Eigenschaften von durch Morphismen definierten Sprachen (Combinatorial properties of languages defined by morphisms)

(bis 12/98)

An important part of formal language theory is concerned with the combinatorial structure of languages. One of the most basic combinatorial properties of a language is the repetition of subwords. Accordingly, a language L is called repetitive if, for each positive integer n, there exists a word w \in L that contains a subword of the form x^n for some non-empty word x. Already Axel Thue studied the repetition of subwords in (infinite) words. Actually he was interested in obtaining long words without repetitions, so-called square-free words.

For context-free languages repetition of subwords is a very natural property. Indeed a context-free language is not repetitive if and only if it is finite. This is an immediate consequence of the pumping lemma for context-free languages. Actually, an infinite context-free language L is not only repetitive, but it is even strongly repetitive, that is, there exists a non-empty word x such that x^n is a subword of L for all positive integers n. Hence, a context-free language is repetitive if and only if it is strongly repetitive. This equivalence is not true in general.

The context-free languages are generated by the context-free grammars, which form a special class of N. Chomsky's phrase-structure grammars. However, since the late 1960s also a different approach based on iterating morphisms has been employed successfully to describe and define languages. These are the so-called L-systems, which were intoduced by A. Lindenmayer in connection with biological considerations. The simplest type of L-system is the D0L-system, where a language L is generated from a given word w by iterating a given morphism f, that is, L={f^n (w) | n \ge 0}. Here we are interested in the repetitiveness of languages generated by morphisms and related concepts.

Technische Reports:

Kobayashi, Y. and Otto, F. :
Repetitiveness of languages generated by morphisms.
Mathematische Schriften Kassel 2/97, Universität-GH Kassel, Februar 1997.
Results presented at MFCS'97.

Veröffentlichungen:

Kobayashi, Y. and Otto, F. :
Repetitiveness of languages generated by morphisms
Theoretical Computer Science 2000, 240:337-378.
Kobayashi, Y. and Otto, F. :
Repetitiveness of D0L-languages is decidable in polynomial time.
In Prívara, I. and Ruzicka, P., editors, Mathematical Foundations of Computer Science 1997, Proceedings MFCS'97, Lecture Notes in Computer Science 1295, pages 337-346. Springer-Verlag 1997, Berlin.
Kobayashi, Y., Otto, F., and Séébold, P. :
A complete characterization of repetitive morphisms over the two-letter alphabet.
In Jiang, T. and Lee, D., editors, Computing and Combinatorics, Proceedings COCOON'97, Lecture Notes in Computer Science 1276, pages 393-402. Springer-Verlag, Berlin.