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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of the Proceedings of the Prague Stringology Conference 2014
EditorsJ. Holub, J. Žďárek
Place of PublicationPrague
PublisherPrague Stringology Club
Pages17-29
Number of pages13
Publication statusPublished - 2014
Externally publishedYes
EventPrague Stringology Conference 2014 - Department of Theoretical Computer Science, Czech Technical University, Prague, Czech Republic
Duration: 1 Sep 20143 Sep 2015

Conference

ConferencePrague Stringology Conference 2014
CountryCzech Republic
CityPrague
Period1/09/143/09/15

Fingerprint Dive into the research topics of 'A process-oriented implementation of Brzozowski's DFA construction algorithm'. Together they form a unique fingerprint.

Cite this