2020/11/25 by David Belanger, Ziyuan Gao, Belanger, David +7
Computer Science · #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Machine Learning and Algorithms #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2012.01466
31 pages, 0 figures
openalex publication_date 2020/11/25 · arxiv created 2021/06/18 · arxiv updated 2021/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r.e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r.e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable.