Standard

On Learning Existentially Definable Subsets in a Computable Structure. / Bazhenov, Nikolay; Mustafa, Manat.

Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. Vol. 15764 2025. p. 143-158 (Lecture Notes in Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › Research › peer-review

Harvard

Bazhenov, N & Mustafa, M 2025, On Learning Existentially Definable Subsets in a Computable Structure. in Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. vol. 15764, Lecture Notes in Computer Science, pp. 143-158, 21st Conference on Computability in Europe, Lisbon, Portugal, 14.07.2025. https://doi.org/10.1007/978-3-031-95908-0_11

APA

Bazhenov, N., & Mustafa, M. (2025). On Learning Existentially Definable Subsets in a Computable Structure. In Crossroads of Computability and Logic: Insights, Inspirations, and Innovations (Vol. 15764, pp. 143-158). (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-031-95908-0_11

Vancouver

Bazhenov N, Mustafa M. On Learning Existentially Definable Subsets in a Computable Structure. In Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. Vol. 15764. 2025. p. 143-158. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-95908-0_11

Author

Bazhenov, Nikolay ; Mustafa, Manat. / On Learning Existentially Definable Subsets in a Computable Structure. Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. Vol. 15764 2025. pp. 143-158 (Lecture Notes in Computer Science).

BibTeX

@inbook{f711c56db2d54ecca0cbf5a828c2c159,
title = "On Learning Existentially Definable Subsets in a Computable Structure",
abstract = "The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure . While provided larger and larger pieces of a subset V of the domain of , a learner tries to guess the G{\"o}del number of an -formula which defines V in . In this setting, we consider several classical learning criteria.For a computable structure , we work with the class containing all -definable (without parameters) subsets of . We focus on some familiar classes of structures , including equivalence structures and Boolean algebras. We establish the following results. If the -theory of a structure is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families coincide. If is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families coincide.We build a computable equivalence structure such that is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy such that is confidently learnable. We construct a computable Heyting algebra such that for any computable copy of , the family is not behaviorally correctly learnable.",
author = "Nikolay Bazhenov and Manat Mustafa",
note = "The work was supported by Nazarbayev University Faculty Development Competitive Research Grants 201223FD8823. The work of Bazhenov is supported by the Mathematical Center in Akademgorodok under the agreement No. 075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation. We are grateful to the anonymous referees for their helpful comments.; 21st Conference on Computability in Europe, CiE 2025 ; Conference date: 14-07-2025 Through 18-07-2025",
year = "2025",
month = jun,
day = "20",
doi = "10.1007/978-3-031-95908-0_11",
language = "English",
isbn = "9783031959073",
volume = "15764",
series = "Lecture Notes in Computer Science",
pages = "143--158",
booktitle = "Crossroads of Computability and Logic: Insights, Inspirations, and Innovations",

}

RIS

TY - CHAP

T1 - On Learning Existentially Definable Subsets in a Computable Structure

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

N1 - Conference code: 21

PY - 2025/6/20

Y1 - 2025/6/20

N2 - The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure . While provided larger and larger pieces of a subset V of the domain of , a learner tries to guess the Gödel number of an -formula which defines V in . In this setting, we consider several classical learning criteria.For a computable structure , we work with the class containing all -definable (without parameters) subsets of . We focus on some familiar classes of structures , including equivalence structures and Boolean algebras. We establish the following results. If the -theory of a structure is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families coincide. If is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families coincide.We build a computable equivalence structure such that is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy such that is confidently learnable. We construct a computable Heyting algebra such that for any computable copy of , the family is not behaviorally correctly learnable.

AB - The paper studies learnability from positive data for families of existentially definable subsets in a given computable structure . While provided larger and larger pieces of a subset V of the domain of , a learner tries to guess the Gödel number of an -formula which defines V in . In this setting, we consider several classical learning criteria.For a computable structure , we work with the class containing all -definable (without parameters) subsets of . We focus on some familiar classes of structures , including equivalence structures and Boolean algebras. We establish the following results. If the -theory of a structure is decidable, then the notions of explanatory learnability and behaviorally correct learnability for families coincide. If is a computable equivalence structure, then the notions of vacillatory learnability and behaviorally correct learnability for such families coincide.We build a computable equivalence structure such that is vacillatorily learnable but not explanatorily learnable. We prove that every computable Boolean algebra has a computable isomorphic copy such that is confidently learnable. We construct a computable Heyting algebra such that for any computable copy of , the family is not behaviorally correctly learnable.

UR - https://www.mendeley.com/catalogue/6612b76a-9dc3-3eeb-8204-45e4166e4635/

U2 - 10.1007/978-3-031-95908-0_11

DO - 10.1007/978-3-031-95908-0_11

M3 - Chapter

SN - 9783031959073

VL - 15764

T3 - Lecture Notes in Computer Science

SP - 143

EP - 158

BT - Crossroads of Computability and Logic: Insights, Inspirations, and Innovations

T2 - 21st Conference on Computability in Europe

Y2 - 14 July 2025 through 18 July 2025

ER -

ID: 68292384