An Optimal Parallel Algorithm for Learning DFA
Abstract
Sequential algorithms given by Angluin 1987 and Schapire 1992 learn deterministic nite automata DFA exactly from Membership and Equivalence queries. These algorithms are feasible, in the sense that they take time polynomial in n and m, where n is the number of states of the automaton and m is the length of the longest counterexample to an Equivalence query. This paper studies whether parallelism can lead to substantially more e cient algorithms for the problem. We show that no CRCW PRAM machine using a number of processors polynomial in n and m can identify DFA in on= log n time. Furthermore, this lower bound is tight up to constant factors: we develop a CRCW PRAM learning algorithm that uses polynomially many processors and exactly learns DFA in time On= log n.
Cite
Text
Balcázar et al. "An Optimal Parallel Algorithm for Learning DFA." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181110Markdown
[Balcázar et al. "An Optimal Parallel Algorithm for Learning DFA." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/balcazar1994colt-optimal/) doi:10.1145/180139.181110BibTeX
@inproceedings{balcazar1994colt-optimal,
title = {{An Optimal Parallel Algorithm for Learning DFA}},
author = {Balcázar, José L. and Díaz, Josep and Gavaldà, Ricard and Watanabe, Osamu},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {208-217},
doi = {10.1145/180139.181110},
url = {https://mlanthology.org/colt/1994/balcazar1994colt-optimal/}
}