An optimal parallel algorithm for learning DFA

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).

REFERENCES

• Ang87: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• BDGW92: José L. Balcázar , Josep Díaz , Ricard Gavaldà , Osamu Watanabe, A Note on the Query Complexity of Learning DFA (Extended Abstract), Proceedings of the Third Workshop on Algorithmic Learning Theory, p.53-62, October 20-22, 1992
• BC92: N.H. Bshouty and R. Cleve, "On the exact learning of formulas in parallel'', in Proc. 33rd Annual Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1992, pp. 513-522.
• BGHM93: Nader H. Bshouty , Sally A. Goldman , Thomas R. Hancock , Sleiman Matar, Asking questions to minimize errors, Proceedings of the sixth annual conference on Computational learning theory, p.41-50, July 26-28, 1993, Santa Cruz, California, United States [doi>10.1145/168304.168310]
• HU79: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• JJ92: Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
• KR90: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• RS89: R. L. Rivest , R. E. Schapire, Inference of finite automata using homing sequences, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.411-420, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73047]
• Sch92: Robert E. Schapire, The design and analysis of efficient learning algorithms, MIT Press, Cambridge, MA, 1992
• Val84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• VL88: Jeffrey Scott Vitter , Jyh-Han Lin, Learning in parallel, Proceedings of the first annual workshop on Computational learning theory, p.106-124, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• Wat92: Osamu Watanabe, A framework for polynomial-time query learnability, Mathematical Systems Theory, v.27 n.3, p.211-229, May/June 1994 [doi>10.1007/BF01578843]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification