Prague Stringology Conference 2010
Maxime Crochemore and Dov M. Gabbay
Reactive Links to Save Automata States
| Abstract: |
| The goal of the reactive automata model is to reduce the space required for the implementation of automata. A reactive automaton has extra links whose role is to change the behaviour of the whole automaton. These links do not increase their expressiveness. Typical examples of regular expressions associated with deterministic automata of exponential size according to the length of the expression show that reactive links provide an alternative representation of total linear size. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |