|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.