PSMA: A Parallel Algorithm for Learning Regular Languages
Inferring a regular language from examples and counter-examples is a classicalproblem in grammatical inference. It is also known as a variant of automata syn-thesis or grammar induction problems and corresponds to finding the smallest DFAconsistent with a labelled sample of strings. The best known algorithm to solvethis problem runs in polynomial (but cubic) time, and for large learning samplesthe algorithm cannot be used. We introduce a parallel version of the RPNIalgo-rithm which solves the above question, and we study the main challenges towardparallelization of such class of algorithms to run in a multi-core environment. Wereport experiments showing the viability of the technique.
PSMA: A Parallel Algorithm for Learning Regular Languages
NIPS Workshop on Learning on Cores, Clusters and Clouds
| Authors: | Hasan Ibne Akram, Alban Batard, Colin de la Higuera, and Claudia Eckert |
| Year/month: | 2010/ |
| Booktitle: | NIPS Workshop on Learning on Cores, Clusters and Clouds |
| Address: | Vancouver, BC Canada |
| Fulltext: | click here |
Abstract |
|
| Inferring a regular language from examples and counter-examples is a classicalproblem in grammatical inference. It is also known as a variant of automata syn-thesis or grammar induction problems and corresponds to finding the smallest DFAconsistent with a labelled sample of strings. The best known algorithm to solvethis problem runs in polynomial (but cubic) time, and for large learning samplesthe algorithm cannot be used. We introduce a parallel version of the RPNIalgo-rithm which solves the above question, and we study the main challenges towardparallelization of such class of algorithms to run in a multi-core environment. Wereport experiments showing the viability of the technique. | |
Bibtex:
@inproceedings { Akram2010a,author = { Hasan Ibne Akram and Alban Batard and Colin de la Higuera and Claudia Eckert},
title = { PSMA: A Parallel Algorithm for Learning Regular Languages },
year = { 2010 },
booktitle = { NIPS Workshop on Learning on Cores, Clusters and Clouds },
address = { Vancouver, BC Canada },
url = { http://lccc.eecs.berkeley.edu/Papers/PSMA_LCCC_2010_NIPS.pdf },
}