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.
Cite
Text
Jain and Sharma. "On the Intrinsic Complexity of Language Identification." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181150Markdown
[Jain and Sharma. "On the Intrinsic Complexity of Language Identification." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/jain1994colt-intrinsic/) doi:10.1145/180139.181150BibTeX
@inproceedings{jain1994colt-intrinsic,
title = {{On the Intrinsic Complexity of Language Identification}},
author = {Jain, Sanjay and Sharma, Arun},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {278-286},
doi = {10.1145/180139.181150},
url = {https://mlanthology.org/colt/1994/jain1994colt-intrinsic/}
}