- On the Complexity of Conclusive Update
- Computer Journal
- Volume | Issue number
- 56 | 3
- Pages (from-to)
- Number of pages
- Document type
- Interfacultary Research Institutes
Faculty of Science (FNWI)
- Institute for Logic, Language and Computation (ILLC)
This work is concerned with finite identifiability of languages from positive data. We focus on the characterization of finite identifiability [Mukouchi (1992), Lange and Zeugmann (1992)], which uses definite finite tell-tale sets (DFTTs for short), finite subsets of languages which are uniquely characteristic for them. We introduce preset learners, learning functions that explicitly use (collections of) DFTTs, and, in cases where there exist only finitely many DFTTs for each language, strict preset learners which in each case use this whole finite collection. We also introduce the concept of fastest learner, a learner which comes up with the right conjecture on any input string that objectively leaves only the right choice of language. We study the use of minimal DFTTs and their influence on the speed of finite identification. We show that: (a) in the case of finite collections of finite sets—finding a minimal DFTT is polynomial time computable, while finding a minimal-size DFTT is NP-complete; (b) in the general case—finite identifiability, minimal strict preset finite identifiability and fastest finite identifiability are shown to be mutually nonequivalent. In the end we mention the relevance of this work for dynamic epistemic logic.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.