Názov:On descriptional complexity of infinite words
Vedúci:doc. RNDr. Pavol Ďurią, CScs.
Kµúčové slová:Infinite words, D0L TAG systems, iterating a morphism, substitution, iterating a GSM
Abstrakt:We consider several mechanisms generating infinite words over a finite alphabet in real time. The simplest and most used mechanism is iterating a morphism on free monoid. There are various natural generalizations of this method - e.g. substitutions, periodic iteration of morphisms and iterating a deterministic GSM. All these iterative mechanisms are related and can be unified on the framework of TAG systems. The main result of this thesis is proving the existence of a dense hierarchy within the class of binary infinite words obtained by substitution (CD0L TAG system) - depending on cardinality of the control alphabet. Similarly, there is a dense hierarchy within the class of infinite words obtained by iterating a DGSM - depending on number of states of the DGSM. Since the notion of the state of a DGSM is equivalent to the notion of the letter of the control alphabet of a DGSM TAG system, these are the same results for classes DGSM and binary CD0L.

Súbory diplomovej práce: