Classifying the arithmetical complexity of teaching models

DOI10.1007/978-3-319-46379-7_10MaRDI QIDQ2830273zbMATH OpenOpenAlexFDO

Authors Achilles A. Beros, Ziyuan Gao, Sandra Zilles

Publication date 9 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1610.08590

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational learning theory (68Q32)

Abstract: This paper classifies the complexity of various teaching models by their position in the arithmetical hierarchy. In particular, we determine the arithmetical complexity of the index sets of the following classes: (1) the class of uniformly r.e. families with finite teaching dimension, and (2) the class of uniformly r.e. families with finite positive recursive teaching dimension witnessed by a uniformly r.e. teaching sequence. We also derive the arithmetical complexity of several other decision problems in teaching, such as the problem of deciding, given an effective coding $mathcal{L}_0,mathcal{L}_1,mathcal{L}_2,ldots$ of all uniformly r.e. families, any $e$ such that $mathcal{L}_e=L_0^e,L_1^e,ldots,$, any $i$ and $d$, whether or not the teaching dimension of $L_i^e$ with respect to $mathcal{L}_e$ is upper bounded by $d$.

Recommendations

• Learning theory in the arithmetic hierarchy. II.
• On the complexity of teaching
• Learning theory in the arithmetic hierarchy
• Combinatorial results on the complexity of teaching and learning
• Measuring teachability using variants of the teaching dimension

Cites work

• Distinguishing pattern languages with membership examples
• Indexmengen und Erkennung Rekursiver Funktionen
• Inductive inference of formal languages from positive data
• Language identification in the limit
• Learning theory in the arithmetic hierarchy
• Models of cooperative teaching and learning
• On the complexity of teaching
• Teachability in computational learning
• The position of index sets of identifiable sets in the arithmetical hierarchy
• The synthesis of language learners.

Cited in

(1)

• Finitely distinguishable erasing pattern languages

This page was built for publication: Classifying the arithmetical complexity of teaching models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830273)