Article

Free access

On the intrinsic complexity of language identification

Authors:

Arun SharmaAuthors Info & Claims

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

Pages 278 - 286

https://doi.org/10.1145/180139.181150

Published: 16 July 1994 Publication History

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]

M. Blum. A machine independent theory of the complexity of recursive functions. Journal of the ACM, 14:322-336, 1967.

Digital Library

[4]

J. Case. Periodicity in generations of automata. Mathematical Systems Theory, 8:15-32, 1974.

[5]

J. Case. The power of vacillation. In D. Haussler and L. Pitt, editors, Proceedings of the Workshop on Computational Learning Theory, pages 133-142. Morgan Kaufmann Publishers, Inc., 1988. Expanded in {6}.

Digital Library

[6]

J. Case. The power of vacillation in language learning. Technical Report 93-08, University of Delaware, 1992. Expands on {5}; journal article under review.

Digital Library

[7]

J. Case and C. Lynes. Machine inductive inference and language identification. In M. Nielsen and E. M. Schmidt, editors, Proceedings of the 9th International Colloquium on Automata, Languages and Programming, volume 140, pages 107- 115. Springer-Verlag, Berlin, 1982.

Digital Library

[8]

R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In J. Barzdins and D. Bjorner, editors, Baltic Computer Science. Lecture Notes in Computer Science 502, pages 77-110. Springer-Verlag, 1991.

Digital Library

[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]

J. Hopcroft and J. Ullman. Introduction to Automata Theory Languages and Computation. Addison-Wesley Publishing Company, 1979.

Digital Library

[12]

M. Machtey and P. Young. An Introduction to the General Theory of Algorithms. North Holland, New York, 1978.

Digital Library

[13]

D. Osherson, M. Stob, and S. Weinstein. Systems that Learn, An Introduction to Learning Theory for Cognitive and Computer Scientists. MIT Press, Cambridge, Mass., 1986.

Digital Library

[14]

D. Osherson and S. Weinstein. Criteria of language learning. Informatzon and Control, 52:123- 138, 1982.

[15]

H. Rogers. Theory of Recursive Functions and Effective Computability. McGraw Hill, New York, 1967. Reprinted, MIT Press 1987.

Digital Library

[16]

R. Wiehagen. Identification of formal languages. Lecture Notes in Computer Science, 53:571-579, 1977.

Cited By

Jain SSharma A(2014)The structure of intrinsic complexity of learningJournal of Symbolic Logic10.2307/227563662:4(1187-1201)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2275636
Jain SSharma A(2005)The structure of intrinsic complexity of learningComputational Learning Theory10.1007/3-540-59119-2_176(169-181)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-59119-2_176
Freivalds RKinber ESmith C(2005)On the intrinsic complexity of learningComputational Learning Theory10.1007/3-540-59119-2_175(154-168)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-59119-2_175
Show More Cited By

Index Terms

On the intrinsic complexity of language identification
1. Computing methodologies
  1. Machine learning
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

The Intrinsic Complexity of Language Identification

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 ...
An approach to intrinsic complexity of uniform learning
Algorithmic learning theory

Inductive inference is concerned with algorithmic learning of recursive functions. In the model of learning in the limit a learner successful for a class of recursive functions must eventually find a program for any function in the class from a ...
Characterizing language identification by standardizing operations

Notions from formal language learning theory are characterized in terms of standardizing operations on classes of recursively enumerable languages. Algorithmic identification in the limit of grammars from text presentation of recursively enumerable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

COLT '94: Proceedings of the seventh annual conference on Computational learning theory

July 1994

376 pages

ISBN:0897916557

DOI:10.1145/180139

Chairman:
Manfred Warmuth
Univ. of California, Santa Cruz

Copyright © 1994 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 July 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

7COLT94

Sponsor:

7COLT94: 7th Annual Conference on Computational Learning Theory

July 12 - 15, 1994

New Jersey, New Brunswick, USA

Acceptance Rates

Overall Acceptance Rate 35 of 71 submissions, 49%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
73
Total Downloads

Downloads (Last 12 months)34
Downloads (Last 6 weeks)8

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jain SSharma A(2014)The structure of intrinsic complexity of learningJournal of Symbolic Logic10.2307/227563662:4(1187-1201)Online publication date: 12-Mar-2014
https://doi.org/10.2307/2275636
Jain SSharma A(2005)The structure of intrinsic complexity of learningComputational Learning Theory10.1007/3-540-59119-2_176(169-181)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-59119-2_176
Freivalds RKinber ESmith C(2005)On the intrinsic complexity of learningComputational Learning Theory10.1007/3-540-59119-2_175(154-168)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-59119-2_175
Meyer L(2001)Aspects of complexity of probabilistic learning under monotonicity constraintsTheoretical Computer Science10.1016/S0304-3975(00)00273-5268:2(275-322)Online publication date: 17-Oct-2001
https://dl.acm.org/doi/10.1016/S0304-3975%2800%2900273-5
Meyer LBartlett PMansour Y(1998)Aspects of complexity of conservative probabilistic learningProceedings of the eleventh annual conference on Computational learning theory10.1145/279943.279957(72-78)Online publication date: 24-Jul-1998
https://dl.acm.org/doi/10.1145/279943.279957
Jain SSharma ABlum AKearns M(1996)Elementary formal systems, intrinsic complexity, and procrastinationProceedings of the ninth annual conference on Computational learning theory10.1145/238061.238093(181-192)Online publication date: 1-Jan-1996
https://dl.acm.org/doi/10.1145/238061.238093
Jain SSharma A(1996)The Intrinsic Complexity of Language IdentificationJournal of Computer and System Sciences10.1006/jcss.1996.003052:3(393-402)Online publication date: 1-Jun-1996
https://dl.acm.org/doi/10.1006/jcss.1996.0030

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Figures

Tables

Media

View Table of Conten