Meno:  Miroslava


Priezvisko:  Kemeňová


Názov:  On descriptional complexity of infinite words


Vedúci:  doc. RNDr. Pavol Ďurią, CScs.


Rok:  2006


Blok:  MMI


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.

