Operations on factor automata.

The thesis concerns pattern matching (PM) using factor automata (FA). PM methods often employ pattern or text preprocessing to speed up the PM algorithms. PM using FA is a kind of PM with text preprocessing suitable especially for searching for substrings of the given text, but it can be also used for locating repetitions, for counting the number of occurrences of the pattern in the text, as a part of a compression algorithm, etc. The advantage of the text preprocessing is mostly demonstrated in multiple PM in the same text. Whenever the text is changed during the multiple PM, the FA has to be reconstructed just after the each change in the text. The construction of the whole FA is too time-consuming (the required time is linear with respect to the size of the text), though the change in the text may be very simple. The new approach described in this thesis consists in reflecting the changes in the text directly into the FA resulting there is no longer needed the whole construction of the FA after each change in the text. The reconstruction of the whole automaton is replaced by modification algorithms for each required change in the text. The changes in the text are defined as a text edit operations and the modification algorithms modifies the FA to represent the new text after each such text edit operation. The thesis introduces a theoretical model of relationship between the text and its FA and it describes a general methodology for discovering FA modification algorithms for other text edit operations. This methodology is then used to derive and to describe modification algorithms for four basic text edit operations. It also introduces a new FA construction method.Available from STL Prague, CZ / NTK - National Technical LibrarySIGLECZCzech Republi