JUCS - Journal of Universal Computer Science 2(3): 97-112, doi: 10.3217/jucs-002-03-0097
An Optimal Parallel Algorithm for Learning DFA
expand article infoJosé L. Balcázar‡, Josep Díaz‡, Ricard Gavaldà‡, Osamu Watanabe§
‡ Universitat Politècnica de Catalunya, Spain§ Tokyo Institute of Technology, Japan

Corresponding author: José Balcázar ( balqui@lsi.upc.es )

© José Balcázar, Josep Díaz, Ricard Gavaldà, Osamu Watanabe.
This article is freely available under the J.UCS Open Content License.
Citation: Balcázar JL, Díaz J, Gavaldà R, Watanabe O (1996) An Optimal Parallel Algorithm for Learning DFA. JUCS - Journal of Universal Computer Science 2(3): 97-112. https://doi.org/10.3217/jucs-002-03-0097
Open Access
Abstract
Sequential algorithms given by Angluin (1987) and Schapire (1992) learn deterministic finite 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 efficient 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 o(n/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 O(n/log n).
Keywords
computational learning theory, query learning, membership query, equivalence query, DFA, optimal parallel learning