Learning Families of Algebraic Structures from Text

Bazhenov, Nikolay; Fokina, Ekaterina; Rossegger, Dino; Soskova, Alexandra; Vatev, Stefan

doi:10.1007/978-3-031-64309-5_14

Record link:

http://hdl.handle.net/20.500.12708/208504
https://doi.org/10.34726/8204

Title:

Learning Families of Algebraic Structures from Text

Citation:

Bazhenov, N., Fokina, E., Rossegger, D., Soskova, A., & Vatev, S. (2024). Learning Families of Algebraic Structures from Text. In L. L. Patey, E. Pimentel, L. Galeotti, & F. Manea (Eds.), Twenty Years of Theoretical and Practical Synergies : 20th Conference on Computability in Europe, CiE 2024, Amsterdam, The Netherlands, July 8–12, 2024, Proceedings (pp. 166–178). Springer. https://doi.org/10.34726/8204

reposiTUm DOI:

10.34726/8204

CatalogPlus:

AC17574864

Publisher DOI:

10.1007/978-3-031-64309-5_14

Publication Type:

Inproceedings - Full-Paper Contribution

Language:

English

Authors:

Bazhenov, Nikolay
Fokina, Ekaterina
Rossegger, Dino
Soskova, Alexandra
Vatev, Stefan

Organisational Unit:

E104-02 - Forschungsbereich Computational Logic

Published in:

Twenty Years of Theoretical and Practical Synergies : 20th Conference on Computability in Europe, CiE 2024, Amsterdam, The Netherlands, July 8–12, 2024, Proceedings

ISBN:

978-3-031-64309-5

Volume:

14773

Date (published):

2-Jul-2024

Event name:

20th Conference on Computability in Europe

Event date:

8-Jul-2024 - 12-Jul-2024

Event place:

Amsterdam, Netherlands (the)

Number of Pages:

Publisher:

Springer, Cham

Peer reviewed:

Yes

Keywords:

Algorithmic learning; Infinitary logic; Scott topology

Abstract:

We adapt the classical notion of learning from text to computable structure theory. Our main result is a model-theoretic characterization of the learnability from text for classes of structures. We show that a family of structures is learnable from text if and only if the structures can be distinguished in terms of their theories restricted to positive infinitary Σ2 sentences.

Project title:

Algorithmische Komplexität von Strukturen und deren Äquivalenzrelationen: 101026834 (European Commission)

Research Areas:

Mathematical and Algorithmic Foundations: 100%

Science Branch:

1020 - Informatik: 5%
1010 - Mathematik: 95%

License:

In Copyright

Appears in Collections:

Conference Paper