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

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.