Typed pattern languages and their learnability

Takeshi Koshiba*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationComputational Learning Theory - 2nd European Conference, EuroCOLT 1995, Proceedings
EditorsPaul Vitanyi
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783540591191
Publication statusPublished - 1995 Jan 1
Externally publishedYes
Event2nd European Conference on Computational Learning Theory, EuroCOLT 1995 - Barcelona, Spain
Duration: 1995 Mar 131995 Mar 15

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd European Conference on Computational Learning Theory, EuroCOLT 1995

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Typed pattern languages and their learnability'. Together they form a unique fingerprint.

Cite this