Samenvatting
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.
Originele taal-2 | Engels |
---|---|
Titel | Proceedings of the Proceedings of the Prague Stringology Conference 2014 |
Redacteuren | J. Holub, J. Žďárek |
Plaats van productie | Prague |
Uitgeverij | Prague Stringology Club |
Pagina's | 17-29 |
Aantal pagina's | 13 |
Status | Gepubliceerd - 2014 |
Extern gepubliceerd | Ja |
Evenement | Prague Stringology Conference 2014 - Department of Theoretical Computer Science, Czech Technical University, Prague, Tsjechië Duur: 1 sep. 2014 → 3 sep. 2015 |
Congres
Congres | Prague Stringology Conference 2014 |
---|---|
Land/Regio | Tsjechië |
Stad | Prague |
Periode | 1/09/14 → 3/09/15 |