### Abstract

Original language | English |
---|---|

Title of host publication | Proceedings of the Proceedings of the Prague Stringology Conference 2014 |

Editors | J. Holub, J. Žďárek |

Place of Publication | Prague |

Publisher | Prague Stringology Club |

Pages | 17-29 |

Number of pages | 13 |

Publication status | Published - 2014 |

Externally published | Yes |

Event | Prague Stringology Conference 2014 - Department of Theoretical Computer Science, Czech Technical University, Prague, Czech Republic Duration: 1 Sep 2014 → 3 Sep 2015 |

### Conference

Conference | Prague Stringology Conference 2014 |
---|---|

Country | Czech Republic |

City | Prague |

Period | 1/09/14 → 3/09/15 |

### Fingerprint

### Cite this

*Proceedings of the Proceedings of the Prague Stringology Conference 2014*(pp. 17-29). Prague: Prague Stringology Club.

}

*Proceedings of the Proceedings of the Prague Stringology Conference 2014.*Prague Stringology Club, Prague, pp. 17-29, Prague Stringology Conference 2014, Prague, Czech Republic, 1/09/14.

**A process-oriented implementation of Brzozowski's DFA construction algorithm.** / Strauss, T.; Kourie, D.G.; Watson, B.W.; Cleophas, L.G.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - A process-oriented implementation of Brzozowski's DFA construction algorithm

AU - Strauss, T.

AU - Kourie, D.G.

AU - Watson, B.W.

AU - Cleophas, L.G.

PY - 2014

Y1 - 2014

N2 - A process-algebraic description of Brzozowski's deterministic finite automaton construction algorithm, slightly adapted from a previous version, shows how the algorithm can be structured as a set of communicating processes. This description was used to guide a process-oriented implementation of the algorithm. The performance of the process-oriented algorithm is then compared against the sequential version for a statistically significant number of randomly generated regular expressions. It is shown that the concurrent version of the algorithm outperforms the sequential version both on a multi-processor machine as well as on a single-processor multi-core machine. This is despite the fact that processor allocation and process scheduling cannot be user-optimised but are, instead, determined by the operating system.

AB - A process-algebraic description of Brzozowski's deterministic finite automaton construction algorithm, slightly adapted from a previous version, shows how the algorithm can be structured as a set of communicating processes. This description was used to guide a process-oriented implementation of the algorithm. The performance of the process-oriented algorithm is then compared against the sequential version for a statistically significant number of randomly generated regular expressions. It is shown that the concurrent version of the algorithm outperforms the sequential version both on a multi-processor machine as well as on a single-processor multi-core machine. This is despite the fact that processor allocation and process scheduling cannot be user-optimised but are, instead, determined by the operating system.

M3 - Conference contribution

SP - 17

EP - 29

BT - Proceedings of the Proceedings of the Prague Stringology Conference 2014

A2 - Holub, J.

A2 - Žďárek, J.

PB - Prague Stringology Club

CY - Prague

ER -