6533b858fe1ef96bd12b6787

RESEARCH PRODUCT

Galīgi ģenerēti biideāli un mašīnu invarianto ω-valodu pusrežģis

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ādits, ka galīgi ģenerēti biideāli ir morfisku v;ardu 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