6533b86dfe1ef96bd12ca39b

RESEARCH PRODUCT

Finitely generated bi-ideals and the semilattice of machine invariant ω-languages

subject

description

Disertācijā pētītas bezgalīgu valodu (w-valodu) īpašības. Galvenais pētījuma objekts ir galīgi ģenerēti biideāli - rekurentu vārdu (biideālu) apakšklase, kuru iespējams aprakstīt, lietojot periodisku bāzes virkni. Interesi par šiem vārdiem palielina dažas daudzsološas to kriptogrāfiskas īpašības, kas arī parādītas darbā. Disertācijas galvenais rezultāts ir izšķiramības problēmas risinājums šim vārdiem. Atrasts efektīvs algoritms, kas sniedz atbildi uz jautājumu, vai divas periodiskas biideālu bāzes ģenerē vienu un to pašu bezgalīgo vārdu. Darbā atspoguļoti arī vairāki citi jauni ar biideāliem saistīti rezultāti. Ir parādīts, ka galīgi ģenerēti biideāli ir morfisku vārdu apakšklase un, ka tie ir slēgti attiecībā pret pātveidojumiem ar nobīdes operatoru un morfismiem. Tiek sniegts piemērs, kas parāda, ka galīgi ģenerēti biideāli nav slēgti attiecībā pret pārveidošanu ar transformatoru. Piemērā galīgi ģenerēts biideāls ar transformatora palīdzību tiek pātveidots par Tue-Morsa vārdu. Otra darba daļa saistīta ar mašīnu invarianto w-vārdu klašu struktūras pētījumiem. Jau agrāk pierādīts, ka w-valodas, kas ir slēgtas attiecībā pret pārveidojumiem ar Mīlija mašīnu veido augšējo pusrežģi ar platumu 2. Darbā parādu, ka šis pusrežģis nav modulārs, un kā sekas, nav distributīvs. Atslēgas vārdi: galīgi ģenerēts biideāls, w-valoda, Mīlija mašīna.