The Prague Stringology Conference 2008
Tinus Strauss, Derrick G. Kourie and Bruce W. Watson
A Concurrent Specification of an Incremental DFA Minimisation Algorithm
| Abstract: |
| In this paper a concurrent version of a published sequential incremental deterministic finite automaton minimisation algorithm is developed. Hoare's Communicating Sequential Processes (CSP) is used as the vehicle to specify the concurrent processes.The specification that is proposed is in terms of the composition of a number of concurrent processes, each corresponding to a pair of nodes for which equivalence needs to be determined. Each of these processes are again composed of several other possibly concurrent processes. To facilitate the specification, a new CSP concurrency operator is defined which, in contrast to the conventional CSP concurrency operator, does not require all processes to synchronise on common events. Instead, it is sufficient for any two (or more) processes to synchronise on such events. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |