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 Dive into the research topics of 'CSP for parallelising Brzozowski's DFA construction algorithm'. Together they form a unique fingerprint.

    Cite this