Name
Abstract | ||
|---|---|---|
Sequential algorithms given by Alguin (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/logn) 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/logn). |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1145/180139.181110 | Computational Learning Theory |
Keywords | Field | DocType |
optimal parallel algorithm,constant factor,crcw pram machine,time polynomial,longest counterexample,time o,crcw pram,deterministic finite automaton,processors polynomial,efficient algorithm,equivalence query,lower bound,deterministic finite automata,parallel algorithm,category | Binary logarithm,Discrete mathematics,Polynomial,Upper and lower bounds,Parallel algorithm,Deterministic finite automaton,DFA minimization,Equivalence (measure theory),Counterexample,Mathematics | Journal |
Volume | Issue | ISBN |
2 | 3 | 0-89791-655-7 |
Citations | PageRank | References |
8 | 0.63 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José L. Balcázar | 1 | 701 | 62.06 |
| Josep Díaz | 2 | 53 | 4.90 |
| Ricard Gavaldà | 3 | 1265 | 81.30 |
| Osamu Watanabet | 4 | 8 | 0.63 |