Finite Identification with Positive and with Complete Data
| Autor: | Ana Lucia Vargas-Sandoval, Dick de Jongh |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Complete data
Conjecture Algorithmic learning theory 0102 computer and information sciences 02 engineering and technology Extension (predicate logic) 01 natural sciences Indexed family Combinatorics Identification (information) 010201 computation theory & mathematics Simple (abstract algebra) 0202 electrical engineering electronic engineering information engineering Identifiability 020201 artificial intelligence & image processing Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783662595640 TbiLLC |
| DOI: | 10.1007/978-3-662-59565-7_3 |
| Popis: | We study the differences between finite identifiability of recursive languages with positive and with complete data. In finite families the difference lies exactly in the fact that for positive identification the families need to be anti-chains, while in the infinite case it is less simple, being an anti-chain is no longer a sufficient condition. We also study maximal learnable families, identifiable families with no proper extension which can be identified. We show that these often though not always exist with positive identification, but that with complete data there are no maximal learnable families at all. We also investigate a conjecture of ours, namely that each positively identifiable family has either finitely many or uncountably many maximal noneffectively positively identifiable extensions. We verify this conjecture for the restricted case of families of equinumerous finite languages. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|