Abstract
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 \({\cal L}\)of recursive languages has recursive finite thickness and the equivalence problem for \({\cal L}\) is decidable, then \({\cal 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 k-bounded regular languages. We show that each of these typed pattern languages is conservatively learnable from positive data.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences, Vol. 21, No. 1, pp. 46–62, 1980.
D. Angluin. Inductive inference of formal languages from positive data. Information and Control, Vol. 45, No. 2, pp. 117–135, 1980.
E. M. Gold. Language identification in the limit. Information and Control, Vol. 10, pp. 447–474, 1967.
S. Ginsburg and E. H. Spanier. Bounded ALGOL-like languages. Transactions of the American Mathematical Society, Vol. 113, pp. 333–368, 1964.
M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978.
J. W. Klop. Term rewriting systems: a tutorial. Note CS-N8701, Centre for Mathematics and Computer Science, Amsterdam, 1987.
S. Lange and T. Zeugmann. Types of monotonic language learning and their characterization. In Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, pp. 377–390. ACM Press, 1992.
T. Moriyama and M. Sato. Properties of languages classes with finite elasticity. In Lecture Notes in Artificial Intelligence (ALT'93), Vol. 744, pp. 187–196. Springer-Verlag, 1993.
T. Motoki, T. Shinohara, and K. Wright. The correct definition of finite elasticity: Corrigendum to identification of unions. In Proceedings of the 4th Annual Workshop on Computational Learning Theory, p. 375. Morgan Kaufmann, 1991.
R. P. Nix. Editing by example. ACM Transactions on Programming Languages and Systems, Vol. 7, No. 4, pp. 600–621, 1985.
K. Wright. Identification of unions of languages drawn from an identifiable class. In Proceedings of the 2nd Annual Workshop on Computational Learning Theory, pp. 328–333. Morgan Kaufmann, 1989.
K. Wright. Inductive identification of pattern languages with restricted substitutions. In Proceedings of the 3rd Annual Workshop on Computational Learning Theory, pp. 111–121. Morgan Kaufmann, 1990.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Koshiba, T. (1995). Typed pattern languages and their learnability. In: Vitányi, P. (eds) Computational Learning Theory. EuroCOLT 1995. Lecture Notes in Computer Science, vol 904. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-59119-2_192
Download citation
DOI: https://doi.org/10.1007/3-540-59119-2_192
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-59119-1
Online ISBN: 978-3-540-49195-8
eBook Packages: Springer Book Archive