Vislielākais burtu izmērs
Lielāks burtu izmērs
Burtu standarta izmērs

Māris Valdats - jaunais datorzinātņu doktors

15.05.2019.

2019. gada 10. maijā LU Datorzinātņu promocijas padomē Māris Valdats izstāvēja promocijas darbu "Galīgu automātu pārejas funkcijas sarežģītība" un ieguva doktora zinātnisko grādu. Darba zinātniskais vadītājs - profesors Juris Smotrovs.

Recenzenti: Dr.sc.comp. U. Straujums (LU), Dr.sc.comp. U.Sarkans (Eiropas Bioinformātikas institūts, Lielbritānija), Dr. M. Hirvensalo (Turku Universitāte, Somija).

Promocijas darbā no sarežģītības viedokļa tiek aplūkots galīgu automātu stāvokļu kodēšanas uzdevums: kā galīgu automātu efektīvi aprakstīt ar loģisko elementu shēmu. Lai arī šis jautājums tiek pētīts jau vairāk nekā 60 gadus, tomēr līdz šim tas ir ticis aplūkots tikai no optimizācijas viedokļa, izstrādājot tam dažādus algoritmus.

Tāpēc tiek ieviests un pētīts atbilstošs galīgu automātu un regulāru valodu sarežģītības mērs, BC-sarežģītība, kas pēc būtības ir loģisko elementu skaits galīga automāta pārejas funkcijā, kas izteikta ar loģisko elementu shēmu.
BC-sarežģītība tiek dažādos veidos salīdzināta ar stāvokļu sarežģītību, piemēram, tiek pierādīts, ka galīgu automātu stāvokļu minimizācija var novest pie vairāk nekā polinomiāla to BC-sarežģītības pieauguma.

Galīgi automāti, kas izteikti ar loģisko elementu shēmu, tiek aplūkoti arī no algoritmiskās sarežģītības viedokļa. Tiek pamatots, ka daudzi vienkārši jautājumi (stāvokļu sasniedzamība vai ekvivalence, automāta minimizācija) šādā reprezentācijā ir PSPACE-pilnīgi.