Daži aspekti bezgalīgo vārdu apstrādei ar Mīlija mašīnām
Date
2006
Authors
Belovs, Aleksandrs
Journal Title
Journal ISSN
Volume Title
Publisher
Latvijas Universitāte
Abstract
Darbā ir aplūkota Mīliju mašīnu, kas ir galīgo automātu-transformatoru paveids, uzvedība uz vienpusējiem bezgalīgiem vārdiem.
Ir ievests bezgalīgo vārdu kvazisakārtojums pēc pārstrādāšanas ar Mīlija mašīnu. Ir izpētītas dažas algebriskas īpašības daļējam sakārtojumam, kas rodas pēc faktorizācijas pēc kanoniskas ekvivalences attiecības.
Papildus, ir dabūti kvalitatīvi rezultāti par noteikto, no kombinatorikas puses interesanto vārdu īpašību saglabāšanu, pielietojot tiem Mīlija mašīnas. Visdziļāk ir aplūkota vienmērīgi rekurento vārdu klase. Ir doti divi pieradījumi, šīs īpašības saglabāšanai, ka arī daži kvantitatīvi rezultāti.
The behaviour of a Mealy machine presenting the class of finite automata-transducer on one-sided infinite words is considered in this work. The semiorder of transforming one infinite word into another with a Mealy machine is defined and some algebraic properties of the corresponding poset that is defined with a factorization by a canonical equivalence relation is studied. We are also interested in qualitative results on the preserving of some combinatoric properties of infinite word by the transformation with a Mealy machine. The deepest attention is toward ultimately recurrent words; two proofs of saving this property are given and also some numerical results are considered.
The behaviour of a Mealy machine presenting the class of finite automata-transducer on one-sided infinite words is considered in this work. The semiorder of transforming one infinite word into another with a Mealy machine is defined and some algebraic properties of the corresponding poset that is defined with a factorization by a canonical equivalence relation is studied. We are also interested in qualitative results on the preserving of some combinatoric properties of infinite word by the transformation with a Mealy machine. The deepest attention is toward ultimately recurrent words; two proofs of saving this property are given and also some numerical results are considered.
Description
Keywords
Datorzinātne