Learning Families of Algebraic Structures from Text

2024/02/08 by Bazhenov, Nikolay, Fokina, Ekaterina, Rossegger, Dino +2
#03C57 #03E15 #F.4.1 #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2402.05744

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 Σ₂ sentences.

Related

• Classifying different criteria for learning algebraic structures
• On the Turing complexity of learning finite families of algebraic structures
• Limit Learning Equivalence Structures
• Learnability and Positive Equivalence Relations
• Learning first-order definable concepts over structures of small degree