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