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

Finite automata
Scheduling

Cite this

Strauss, T., Kourie, D. G., Watson, B. W., & Cleophas, L. G. (2014). A process-oriented implementation of Brzozowski's DFA construction algorithm. In J. Holub, & J. Žďárek (Eds.), Proceedings of the Proceedings of the Prague Stringology Conference 2014 (pp. 17-29). Prague: Prague Stringology Club.
Strauss, T. ; Kourie, D.G. ; Watson, B.W. ; Cleophas, L.G. / A process-oriented implementation of Brzozowski's DFA construction algorithm. Proceedings of the Proceedings of the Prague Stringology Conference 2014. editor / J. Holub ; J. Žďárek. Prague : Prague Stringology Club, 2014. pp. 17-29
@inproceedings{56cd590d83414ec184c0a5bcae4b63e4,
title = "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.",
author = "T. Strauss and D.G. Kourie and B.W. Watson and L.G. Cleophas",
year = "2014",
language = "English",
pages = "17--29",
editor = "J. Holub and J. Žď{\'a}rek",
booktitle = "Proceedings of the Proceedings of the Prague Stringology Conference 2014",
publisher = "Prague Stringology Club",

}

Strauss, T, Kourie, DG, Watson, BW & Cleophas, LG 2014, A process-oriented implementation of Brzozowski's DFA construction algorithm. in J Holub & J Žďárek (eds), Proceedings of the Proceedings of the Prague Stringology Conference 2014. Prague Stringology Club, Prague, pp. 17-29, Prague Stringology Conference 2014, Prague, Czech Republic, 1/09/14.

A process-oriented implementation of Brzozowski's DFA construction algorithm. / Strauss, T.; Kourie, D.G.; Watson, B.W.; Cleophas, L.G.

Proceedings of the Proceedings of the Prague Stringology Conference 2014. ed. / J. Holub; J. Žďárek. Prague : Prague Stringology Club, 2014. p. 17-29.

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

TY - GEN

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

AU - Strauss, T.

AU - Kourie, D.G.

AU - Watson, B.W.

AU - Cleophas, L.G.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 17

EP - 29

BT - Proceedings of the Proceedings of the Prague Stringology Conference 2014

A2 - Holub, J.

A2 - Žďárek, J.

PB - Prague Stringology Club

CY - Prague

ER -

Strauss T, Kourie DG, Watson BW, Cleophas LG. A process-oriented implementation of Brzozowski's DFA construction algorithm. In Holub J, Žďárek J, editors, Proceedings of the Proceedings of the Prague Stringology Conference 2014. Prague: Prague Stringology Club. 2014. p. 17-29