|
|
Efficient Algorithms for Büchi Automata
Laščák, Tomáš ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
The main goal of this work is to extend the existing library VATA with a module for working with Büchi automata, which are finite state automata over infinite words. These automata are used in many areas of computer science, among others in formal verifications, namely in LTL model checking. LTL model checking is typically carried out using the operation of testing language inclusion between two Büchi automata. Because testing language inclusion can be computationally very demanding, several optimized algorithms have been created for testing language inclusion such as the Ramsey-based approach. This work is focused on the mentioned approach, the implementation of which is added to the newly created extension of the VATA library. Apart from that, the new extension adds additional useful operations over Büchi automata such as union, intersection or a reduction in the number of states.
|
|
|
Web Page Segmentation Algorithms
Laščák, Tomáš ; Burgetová, Ivana (referee) ; Burget, Radek (advisor)
Segmentation of web pages is one of the disciplines of information extraction. It allows to divide the page into different semantic blocks. This thesis deals with the segmentation as such and also with the implementation of the segmentation method. In this paper, we describe various examples of methods such as VIPS, DOM PS etc. There is a theoretical description of the chosen method and also the FITLayout Framework, which will be extended by this method. The implementation of the chosen method is also described in detail. The implementation description is focused on describing the different problems we had to solve. We also describe the testing that helped to reveal some weaknesses. The conclusion is a summary of the results and possible ideas for extending this work.
|
|
|
Efficient Algorithms for Büchi Automata
Laščák, Tomáš ; Holík, Lukáš (referee) ; Lengál, Ondřej (advisor)
The main goal of this work is to extend the existing library VATA with a module for working with Büchi automata, which are finite state automata over infinite words. These automata are used in many areas of computer science, among others in formal verifications, namely in LTL model checking. LTL model checking is typically carried out using the operation of testing language inclusion between two Büchi automata. Because testing language inclusion can be computationally very demanding, several optimized algorithms have been created for testing language inclusion such as the Ramsey-based approach. This work is focused on the mentioned approach, the implementation of which is added to the newly created extension of the VATA library. Apart from that, the new extension adds additional useful operations over Büchi automata such as union, intersection or a reduction in the number of states.
|
|
|
Web Page Segmentation Algorithms
Laščák, Tomáš ; Burgetová, Ivana (referee) ; Burget, Radek (advisor)
Segmentation of web pages is one of the disciplines of information extraction. It allows to divide the page into different semantic blocks. This thesis deals with the segmentation as such and also with the implementation of the segmentation method. In this paper, we describe various examples of methods such as VIPS, DOM PS etc. There is a theoretical description of the chosen method and also the FITLayout Framework, which will be extended by this method. The implementation of the chosen method is also described in detail. The implementation description is focused on describing the different problems we had to solve. We also describe the testing that helped to reveal some weaknesses. The conclusion is a summary of the results and possible ideas for extending this work.
|
guest ::
