0000000000204663
AUTHOR
Māris Valdats
showing 2 related works from this author
Descriptional and Computational Complexity of the Circuit Representation of Finite Automata
2018
In this paper we continue to investigate the complexity of the circuit representation of DFA—BC-complexity. We compare it with nondeterministic state complexity, obtain upper and lower bounds which differ only by a factor of 4 for a Binary input alphabet. Also we prove that many simple operations (determining if a state is reachable or if an automaton is minimal) are PSPACE-complete for DFA given in circuit representation.
Galīgu automātu pārejas funkcijas sarežģītība
2019
Š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 e…