TY - GEN

T1 - Typed pattern languages and their learnability

AU - Koshiba, Takeshi

PY - 1995/1/1

Y1 - 1995/1/1

N2 - In this paper, we extend patterns, introduced by Angluin [Ang80b], to typed patterns by introducing types into variables. A type is a recursive language and a variable of the type is substituted only with an element in the recursive language. This extension enhances the expressive power of patterns with preserving their good properties. First, we give a general learnability result for typed pattern languages. We show that if a class of types has finite elasticity then the typed pattern language is identifiable in the limit from positive data. Next, we give a useful tool to show the conservative learnability of typed pattern languages. That is, if an indexed family L of recursive languages has recursive finite thickness and the equivalence problem for L is decidable, then L is conservatively learnable from positive data. Using this tool, we consider the following classes of types: (1) the class of all strings over subsets of the alphabet, (2) the class of all untyped pattern languages, and (3) a class of ĸ-bounded regular languages. We show that each of these typed pattern languages is conservatively learnable from positive data.

AB - In this paper, we extend patterns, introduced by Angluin [Ang80b], to typed patterns by introducing types into variables. A type is a recursive language and a variable of the type is substituted only with an element in the recursive language. This extension enhances the expressive power of patterns with preserving their good properties. First, we give a general learnability result for typed pattern languages. We show that if a class of types has finite elasticity then the typed pattern language is identifiable in the limit from positive data. Next, we give a useful tool to show the conservative learnability of typed pattern languages. That is, if an indexed family L of recursive languages has recursive finite thickness and the equivalence problem for L is decidable, then L is conservatively learnable from positive data. Using this tool, we consider the following classes of types: (1) the class of all strings over subsets of the alphabet, (2) the class of all untyped pattern languages, and (3) a class of ĸ-bounded regular languages. We show that each of these typed pattern languages is conservatively learnable from positive data.

UR - http://www.scopus.com/inward/record.url?scp=84955606048&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955606048&partnerID=8YFLogxK

U2 - 10.1007/3-540-59119-2_192

DO - 10.1007/3-540-59119-2_192

M3 - Conference contribution

AN - SCOPUS:84955606048

SN - 9783540591191

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 367

EP - 379

BT - Computational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings

A2 - Vitanyi, Paul

PB - Springer Verlag

T2 - 2nd European Conference on Computational Learning Theory, EuroCOLT 1995

Y2 - 13 March 1995 through 15 March 1995

ER -