|
|
Minimization of Counting Automata
Turcel, Matej ; Vojnar, Tomáš (oponent) ; Holík, Lukáš (vedoucí práce)
This works deals with size reduction of counting automata (CA). Counting automata extend the classical finite automata with bounded counters. This allows efficient handling of e.g. regular expressions with repetition: a{5,10}. In this thesis we discusses the simulation relation in CA, which allows us to reduce their size. We rely on classical simulation in finite automata, which we non-trivially extend to CA. The key difference lies in the necessity to simulate counters as well as states. To this end, we present the novel concept of parameterized simulation relation in CA, and propose methods for computing this relation and using it to reduce the size of a CA. The proposed methods have been implemented and their efficiency experimentally evaluated.
|
|
|
Simulace pro symbolické automaty
Síč, Juraj ; Lengál, Ondřej (oponent) ; Holík, Lukáš (vedoucí práce)
Symbolické automaty sú podobné klasickým automatom s jedným veľkým rozdielom: prechody sú značené predikátmi definovanými v oddelenej teórii. Toto umožňuje použiť veľké abecedy s pouźitím oveľa menšieho miesta. V tejto práci sa zaoberáme výpočtom simulácie (binárnej relácie nad množinou stavov, ktorá aproximuje jazykovú inklúziu) pre tieto automaty. Táto relácia sa dá potom použiť pri redukovaní počtu stavov bez nutnosti determinizácie. Existuje niekoľko algoritomv pre výpočet simulácie pre Kripkeho štruktúry, ktoré boli neskôr modifikované pre označené prechodové systémy a klasické automaty. V tejto práci ukážeme ako sa dá jeden z týchto algoritmov modifikovať pre symbolické automaty použitím rozkladu domény abecedy ktorý je kompatibilný s predikátmi značiacimi prechody a použitím možností teórie abecedy.
|
|
|
Minimization of Counting Automata
Turcel, Matej ; Vojnar, Tomáš (oponent) ; Holík, Lukáš (vedoucí práce)
This works deals with size reduction of counting automata (CA). Counting automata extend the classical finite automata with bounded counters. This allows efficient handling of e.g. regular expressions with repetition: a{5,10}. In this thesis we discusses the simulation relation in CA, which allows us to reduce their size. We rely on classical simulation in finite automata, which we non-trivially extend to CA. The key difference lies in the necessity to simulate counters as well as states. To this end, we present the novel concept of parameterized simulation relation in CA, and propose methods for computing this relation and using it to reduce the size of a CA. The proposed methods have been implemented and their efficiency experimentally evaluated.
|
|
|
Minimization of Counting Automata
Turcel, Matej ; Vojnar, Tomáš (oponent) ; Holík, Lukáš (vedoucí práce)
This works deals with size reduction of counting automata (CA). Counting automata extend the classical finite automata with bounded counters. This allows efficient handling of e.g. regular expressions with repetition: a{5,10}. In this thesis we discusses the simulation relation in CA, which allows us to reduce their size. We rely on classical simulation in finite automata, which we non-trivially extend to CA. The key difference lies in the necessity to simulate counters as well as states. To this end, we present the novel concept of parameterized simulation relation in CA, and propose methods for computing this relation and using it to reduce the size of a CA. The proposed methods have been implemented and their efficiency experimentally evaluated.
|
|
|
Minimization of Counting Automata
Turcel, Matej ; Vojnar, Tomáš (oponent) ; Holík, Lukáš (vedoucí práce)
This works deals with size reduction of counting automata (CA). Counting automata extend the classical finite automata with bounded counters. This allows efficient handling of e.g. regular expressions with repetition: a{5,10}. In this thesis we discusses the simulation relation in CA, which allows us to reduce their size. We rely on classical simulation in finite automata, which we non-trivially extend to CA. The key difference lies in the necessity to simulate counters as well as states. To this end, we present the novel concept of parameterized simulation relation in CA, and propose methods for computing this relation and using it to reduce the size of a CA. The proposed methods have been implemented and their efficiency experimentally evaluated.
|
|
|
Simulace pro symbolické automaty
Síč, Juraj ; Lengál, Ondřej (oponent) ; Holík, Lukáš (vedoucí práce)
Symbolické automaty sú podobné klasickým automatom s jedným veľkým rozdielom: prechody sú značené predikátmi definovanými v oddelenej teórii. Toto umožňuje použiť veľké abecedy s pouźitím oveľa menšieho miesta. V tejto práci sa zaoberáme výpočtom simulácie (binárnej relácie nad množinou stavov, ktorá aproximuje jazykovú inklúziu) pre tieto automaty. Táto relácia sa dá potom použiť pri redukovaní počtu stavov bez nutnosti determinizácie. Existuje niekoľko algoritomv pre výpočet simulácie pre Kripkeho štruktúry, ktoré boli neskôr modifikované pre označené prechodové systémy a klasické automaty. V tejto práci ukážeme ako sa dá jeden z týchto algoritmov modifikovať pre symbolické automaty použitím rozkladu domény abecedy ktorý je kompatibilný s predikátmi značiacimi prechody a použitím možností teórie abecedy.
|
host ::
RSS.