Name
Abstract | ||
|---|---|---|
In this paper two concurrent versions of Brzozowski's deterministic finite automaton (DFA) construction algorithm are developed from first principles, the one being a slight refinement of the other. We rely on Hoare's CSP as our notation.The specifications that are proposed of the Brzozowski algorithm are in terms of the concurrent composition of a number of top-level processes, each participating process itself composed of several other concurrent processes. After considering a number of alternatives, this particular overall architectural structure seemed like a natural and elegant mapping from the sequential algorithm's structure.While we have carefully argued the reasons for constructing the concurrent versions as proposed in the paper, there are of course, a large range of alternative design choices that could be made. There might also be scope for a more fine-grained approach to updating sets or checking for similarity of regular expressions. At this stage, we have chosen to abstract away from these considerations, and leave their exploration for a subsequent step in our research. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1142/S0129054108005577 | INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE |
Keywords | DocType | Volume |
automaton construction, concurrency, CSP, regular expressions | Journal | 19 |
Issue | ISSN | Citations |
1 | 0129-0541 | 0 |
PageRank | References | Authors |
0.34 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tinus Strauss | 1 | 12 | 5.35 |
| Derrick G. Kourie | 2 | 223 | 33.10 |
| Bruce W. Watson | 3 | 338 | 53.24 |