CSP for parallelising Brzozowski's DFA construction algorithm

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureHoofdstukAcademicpeer review

Samenvatting


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.


Originele taal-2Engels
TitelThe Role of Theory in Computer Science : Essays Dedicated to Janusz Brzozowski
Plaats van producties.l.
UitgeverijWorld Scientific
Pagina's217-244
Aantal pagina's28
ISBN van elektronische versie978-981-3148-21-5
ISBN van geprinte versie978-981-3148-19-2
DOI's
StatusGepubliceerd - 2017

Vingerafdruk Duik in de onderzoeksthema's van 'CSP for parallelising Brzozowski's DFA construction algorithm'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    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 (blz. 217-244). World Scientific. https://doi.org/10.1142/9789813148208_0010