On the intrinsic complexity of language identification

ABSTRACT

A new investigation of the complexity of language identification is undertaken using the notion of reduction from recursion theory and complexity theory. The approach, referred to as the intrinsic complexity of language identification, employs notions of “weak” and “strong” reduction between learnable classes of languages. The intrinsic complexity of several classes are considered and the results agree with the intuitive difficulty of learning these classes. Several complete classes are shown for both the reductions and it is also established that the weak and strong reductions are distinct. An interesting result is that the self referential class of Wiehagen in which the minimal element of every language is a grammar for the language and the class of pattern languages introduced by Angluin are equivalent in the strong sense. This study has been influenced by a similar treatment of function identification by Freivalds, Kinber, and Smith.

REFERENCES

• 1: D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, 21:46-62, 1980.
• 2: D. Angluin. Inductive inference of formal languages from positive data. Information and Control, 45:117-135, 1980.
• 3: Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
• 4: J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15-32, 1974.
• 5: John Case, The power of vacillation, Proceedings of the first annual workshop on Computational learning theory, p.196-205, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 6: John Case, The power of vacillation, Proceedings of the first annual workshop on Computational learning theory, p.196-205, August 03-05, 1988, MIT, Cambridge, Massachusetts, United States
• 7: John Case , Christopher Lynes, Machine Inductive Inference and Language Identification, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.107-115, July 12-16, 1982
• 8: Rusins Freivalds, Inductive Inference of Recursive Functions: Qualitative Theory, Baltic Computer Science, Selected Papers, p.77-110, January 1991
• 9: R Freivalds, E. Kinber, and C. H. Smith. On the intrinsic complexity of learning. Technical Report 94-24, University of Delaware, Newark, Delaware, 1994.
• 10: E. M. Gold. Language identification in the limit. Information and Control, 10:447-474, 1967.
• 11: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 12: Michael Machtey , Paul Young, An Introduction to the General Theory of Algorithms, Elsevier Science Inc., New York, NY, 1978
• 13: Daniel N. Osherson , Michael Stob , Scott Weinstein, Systems that learn: an introduction to learning theory for cognitive and computer scientists, MIT Press, Cambridge, MA, 1986
• 14: D. Osherson and S. Weinstein. Criteria of language learning. Informatzon and Control, 52:123- 138, 1982.
• 15: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 16: R. Wiehagen. Identification of formal languages. Lecture Notes in Computer Science, 53:571-579, 1977.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Theory, Verification