CSP for parallelising Brzozowski's DFA construction algorithm

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

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

Abstract


CSP, a simple and elegant process algebra, is used to specify five successive parallel versions of Brzozowski’s sequential algorithm for constructing deterministic finite automata from regular expressions. Early versions were not sufficiently mature to easily map to a programming language. However, each version exposed new possibilities for refinement so that later versions could subsequently be implemented (in Go). The exercise illustrates the value of the lightweight use of process algebras for supporting abstract thinking when attempting to solve computational problems in a parallel fashion. The emphasis here is on algorithm specification and not on the implementation.


Original languageEnglish
Title of host publicationThe Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski
Place of Publications.l.
PublisherWorld Scientific
Pages217-244
Number of pages28
ISBN (Electronic)978-981-3148-21-5
ISBN (Print)978-981-3148-19-2
DOIs
Publication statusPublished - 2017

Fingerprint

Algebra
Finite automata
Computer programming languages
Specifications

Cite this

Strauss, T., Watson, B. W., Kourie, D. G., & Cleophas, L. G. W. A. (2017). CSP for parallelising Brzozowski's DFA construction algorithm. In The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski (pp. 217-244). s.l.: World Scientific. https://doi.org/10.1142/9789813148208_0010
Strauss, T. ; Watson, B.W. ; Kourie, D.G. ; Cleophas, L.G.W.A. / CSP for parallelising Brzozowski's DFA construction algorithm. The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski. s.l. : World Scientific, 2017. pp. 217-244
@inbook{f6201f3b4fde487ba96f506efb108e2a,
title = "CSP for parallelising Brzozowski's DFA construction algorithm",
abstract = "CSP, a simple and elegant process algebra, is used to specify five successive parallel versions of Brzozowski’s sequential algorithm for constructing deterministic finite automata from regular expressions. Early versions were not sufficiently mature to easily map to a programming language. However, each version exposed new possibilities for refinement so that later versions could subsequently be implemented (in Go). The exercise illustrates the value of the lightweight use of process algebras for supporting abstract thinking when attempting to solve computational problems in a parallel fashion. The emphasis here is on algorithm specification and not on the implementation.",
author = "T. Strauss and B.W. Watson and D.G. Kourie and L.G.W.A. Cleophas",
year = "2017",
doi = "10.1142/9789813148208_0010",
language = "English",
isbn = "978-981-3148-19-2",
pages = "217--244",
booktitle = "The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski",
publisher = "World Scientific",
address = "United States",

}

Strauss, T, Watson, BW, Kourie, DG & Cleophas, LGWA 2017, CSP for parallelising Brzozowski's DFA construction algorithm. in The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski. World Scientific, s.l., pp. 217-244. https://doi.org/10.1142/9789813148208_0010

CSP for parallelising Brzozowski's DFA construction algorithm. / Strauss, T.; Watson, B.W.; Kourie, D.G.; Cleophas, L.G.W.A.

The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski. s.l. : World Scientific, 2017. p. 217-244.

Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

TY - CHAP

T1 - CSP for parallelising Brzozowski's DFA construction algorithm

AU - Strauss, T.

AU - Watson, B.W.

AU - Kourie, D.G.

AU - Cleophas, L.G.W.A.

PY - 2017

Y1 - 2017

N2 - CSP, a simple and elegant process algebra, is used to specify five successive parallel versions of Brzozowski’s sequential algorithm for constructing deterministic finite automata from regular expressions. Early versions were not sufficiently mature to easily map to a programming language. However, each version exposed new possibilities for refinement so that later versions could subsequently be implemented (in Go). The exercise illustrates the value of the lightweight use of process algebras for supporting abstract thinking when attempting to solve computational problems in a parallel fashion. The emphasis here is on algorithm specification and not on the implementation.

AB - CSP, a simple and elegant process algebra, is used to specify five successive parallel versions of Brzozowski’s sequential algorithm for constructing deterministic finite automata from regular expressions. Early versions were not sufficiently mature to easily map to a programming language. However, each version exposed new possibilities for refinement so that later versions could subsequently be implemented (in Go). The exercise illustrates the value of the lightweight use of process algebras for supporting abstract thinking when attempting to solve computational problems in a parallel fashion. The emphasis here is on algorithm specification and not on the implementation.

U2 - 10.1142/9789813148208_0010

DO - 10.1142/9789813148208_0010

M3 - Chapter

SN - 978-981-3148-19-2

SP - 217

EP - 244

BT - The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski

PB - World Scientific

CY - s.l.

ER -

Strauss T, Watson BW, Kourie DG, Cleophas LGWA. CSP for parallelising Brzozowski's DFA construction algorithm. In The Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski. s.l.: World Scientific. 2017. p. 217-244 https://doi.org/10.1142/9789813148208_0010