• English
    • Latviešu
    • Deutsch
    • русский
  • Help
  • русский 
    • English
    • Latviešu
    • Deutsch
    • русский
  • Войти
Просмотр элемента 
  •   Главная
  • A2 – LU disertācijas / Doctoral theses UL
  • Promocijas darbi (2007-) / Theses PhD
  • Просмотр элемента
  •   Главная
  • A2 – LU disertācijas / Doctoral theses UL
  • Promocijas darbi (2007-) / Theses PhD
  • Просмотр элемента
JavaScript is disabled for your browser. Some features of this site may not work without it.

Galīgu automātu pārejas funkcijas sarežģītība

Thumbnail
Открыть
298-69075-Valdats_Maris_mv07090.pdf (901.4Kb)
Автор
Valdats, Māris
Co-author
Latvijas Universitāte. Datorikas fakultāte
Advisor
Smotrovs, Juris
Дата
2019
Metadata
Показать полную информацию
Аннотации
Šajā darbā no sarežģītības viedokļa tiek aplūkots galīgu automātu stāvokļu kodēšanas uzdevums. 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. Regulāru valodu BC-sarežģītība ir novērtēta attiecībā pret stāvokļu sarežģītību un tai tiek iegūtas sakrītošas augšējās un apakšējās robežas gandrīz visām valodām ar doto stāvokļu sarežģītību. Tiek pierādīts, ka galīgu automātu 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. Atslēgas vārdi: Galīgs automāts, loģiskā shēma, sarežģītība
 
This thesis considers the state assignment problem of finite automata from the complexity point of view. For that a new complexity measure for finite automata and regular languages, BC-complexity, is introduced. BC-complexity of regular languages is compared with their state complexity and matching upper and lower bounds are obtained for almost all languages with given state complexity. It is proved that the minimization of finite automata can lead to a superpolynomial increase of their BC-complexity. Finite automata represented with a Boolean circuit are considered also from the computational complexity point of view. It is shown that many simple problems (state reachability or equivalence, minimization of automata) in this representation are PSPACE-complete. keywords: Finite automata, Circuits, Complexity
 
URI
https://dspace.lu.lv/dspace/handle/7/48852
Collections
  • Promocijas darbi (2007-) / Theses PhD [1374]

University of Latvia
Контакты | Отправить отзыв
Theme by 
@mire NV
 

 

Просмотр

Весь DSpaceСообщества и коллекцииДата публикацииАвторыНазванияТематикаЭта коллекцияДата публикацииАвторыНазванияТематика

Моя учетная запись

Войти

Статистика

Просмотр статистики использования

University of Latvia
Контакты | Отправить отзыв
Theme by 
@mire NV