PSMA: A Parallel Algorithm for Learning Regular Languages
Inferring a regular language from examples and counterexamples is a classicalproblem in grammatical inference. It is also known as a variant of automata synthesis 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 RPNIalgorithm which solves the above question, and we study the main challenges towardparallelization of such class of algorithms to run in a multicore 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 counterexamples is a classicalproblem in grammatical inference. It is also known as a variant of automata synthesis 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 RPNIalgorithm which solves the above question, and we study the main challenges towardparallelization of such class of algorithms to run in a multicore 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 },
}