A process-oriented implementation of Brzozowski's DFA construction algorithm

T. Strauss, D.G. Kourie, B.W. Watson, L.G. Cleophas

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

2 Citaten (Scopus)
2 Downloads (Pure)

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-2Engels
TitelProceedings of the Proceedings of the Prague Stringology Conference 2014
RedacteurenJ. Holub, J. Žďárek
Plaats van productiePrague
UitgeverijPrague Stringology Club
Pagina's17-29
Aantal pagina's13
StatusGepubliceerd - 2014
Extern gepubliceerdJa
EvenementPrague Stringology Conference 2014 - Department of Theoretical Computer Science, Czech Technical University, Prague, Tsjechië
Duur: 1 sep. 20143 sep. 2015

Congres

CongresPrague Stringology Conference 2014
Land/RegioTsjechië
StadPrague
Periode1/09/143/09/15

Vingerafdruk

Duik in de onderzoeksthema's van 'A process-oriented implementation of Brzozowski's DFA construction algorithm'. Samen vormen ze een unieke vingerafdruk.

Citeer dit