On the Amount of Nonconstructivity in Learning Formal Languages from Positive Data

Authors: Sanjay Jain, Frank Stephan, and and Thomas Zeugmann

Source: Theory and Applications of Models of Computation,
9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012, Proceedings,
(Manindra Agrawal and S. Barry Cooper and Ansheng Li, Eds.) Lecture Notes in Computer Science 7287, pp. 423--434, Springer 2012.

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 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 from positive data. 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.

This research was performed partially while the third author was visiting the Institute of Mathematical Sciences at the National University of Singapore in September 2011. His visit was supported by the Institute. Sanjay Jain was supported in part by NUS grant numbers C252-000-087-001 and R252-000-420-112, and Frank Stephan was supported in part by NUS grant number R252-000-420-112.