TCS-TR-A-12-55

Date: Mon Mar 12 20:27:45 2012

Title: On the Amount of Nonconstructivity in Learning Formal Languages from Text

Authors: Sanjay Jain, Frank Stephan, and Thomas Zeugmann

Contact:

First name: Thomas
Last name: Zeugmann
Address: Division of Computer Science, Hokkaido University, N-14, W-9, Sapporo 060-0814, Japan
Email: thomas@ist.hokudai.ac.jp

Abstract. Nonconstructive computations by various types of machines and automata have been considered by e.g., Karp and Lipton (1982) and Freivalds (2009, 2010). They allow to regard more complicated algorithms from the viewpoint of much more primitive computational devices. The amount of nonconstructivity is a quantitative characterization of the distance between types of computational devices with respect to solving a specific problem. This paper studies the amount of nonconstructivity needed to learn classes of formal languages. Different learning types are compared with respect to the amount of nonconstructivity needed to learn indexable classes and recursively enumerable classes, respectively, of formal languages from positive data. Matching upper and lower bounds for the amount of nonconstructivity needed are shown.