Prague Stringology Conference 2014
Tinus Strauss, Derrick G. Kourie, Bruce W. Watson and Loek Cleophas
A Process-Oriented Implementation of Brzozowski's DFA Construction Algorithm
| Abstract: |
| A process-algebraic description of Brzozowski's deterministic finite automaton construction algorithm, slightly adapted from a previous version, shows how the algorithm can be structured as a set of communicating processes. This description was used to guide a process-oriented implementation of the algorithm. The performance of the process-oriented algorithm is then compared against the sequential version for a statistically significant number of randomly generated regular expressions. It is shown that the concurrent version of the algorithm outperforms the sequential version both on a multi-processor machine as well as on a single-processor multi-core machine. This is despite the fact that processor allocation and process scheduling cannot be user-optimised but are, instead, determined by the operating system. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |