106 research outputs found
Mind change speed-up for learning languages from positive data
No full text10.1016/j.tcs.2013.04.009Theoretical Computer Science489-49037-47TCSC
Theory of Computing: A Gentle Introduction
No full textUnderstanding the fundamentals of computations is central to understanding the rapidly changing practice of computing. In this text, Kinber and Smith present largely traditional material in a dynamic how to rather than the typical why for fashion. Intuition has been chosen over rigor in an effort to enhance comprehension by those with less extensive mathematical training. The authors rely heavily on figures and examples to lead the reader to insights typically revealed by formal arguments. Using this approach, Kinber and Smith explain the fundamental intuitions of computation. --Book jacket
Learning Recursive Functions from Approximations (Extended Abstract)
No full text) Appeared In: EuroCOLT'95, LNCS 904, 140--153, Springer-Verlag, 1995. John Case 1 , Susanne Kaufmann 2 , Efim Kinber 1 , Martin Kummer 2 1 Department of Computer and Information Sciences, University of Delaware, Newark, Delaware 19176, USA. fcase; [email protected] 2 Institut fur Logik, Komplexitat und Deduktionssysteme, Universitat Karlsruhe, D-76128 Karlsruhe, Germany. fkaufmann; [email protected] Abstract. Investigated is algorithmic learning, in the limit, of correct programs for recursive functions f from both input/output examples of f and several interesting varieties of approximate additional (algorithmic) information about f . Specifically considered, as such approximate additional information about f , are Rose's frequency computations for f and several natural generalizations from the literature, each generalization involving programs for restricted trees of recursive functions which have f as a branch. Considered as the types of trees are those w..
On the classification of recursive languages
No full textAbstractA one-sided classifier for a given class of languages converges to 1 on every language from the class and outputs 0 infinitely often on languages outside the class. A two-sided classifier, on the other hand, converges to 1 on languages from the class and converges to 0 on languages outside the class. The present paper investigates one-sided and two-sided classification for classes of recursive languages. Theorems are presented that help assess the classifiability of natural classes. The relationships of classification to inductive learning theory and to structural complexity theory in terms of Turing degrees are studied. Furthermore, the special case of classification from only positive data is also investigated
TRA8/05 Variations on U-shaped Learning
No full texttutorial article, which has been submitted for publication in a journal or for consideration by the commissioning organization. The report represents the ideas of its author, and should not be taken as the official views of the School or the University. Any discussion of the content of the report should be sent to the author, at the address shown on the cover. JAFFAR, Joxa
Learning Regular Expressions from Representative Examples and Membership Queries
No full textA learning algorithm is developed for a class of regular expressions equivalent to the class of all unionless unambiguous regular expressions of loop depth 2. The learner uses one representative example of the target language (where every occurrence of every loop in the target expression is unfolded at least twice) and a number of membership queries. The algorithm works in time polynomial in the length of the input example
- …
