Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLimit Learning Equivalence Structures
133
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
While most research in Gold-style learning focuses on learning formal languages, we consider the identification of computable structures, specifically equivalence structures. In our core model the learner gets more and more information about which pairs of elements of a structure are related and which are not. The aim of the learner is to find (an effective description of) the isomorphism type of the structure presented in the limit. In accordance with language learning we call this learning criterion InfEx-learning (explanatory learning from informant). Our main contribution is a complete characterization of which families of equivalence structures are InfEx-learnable. This characterization allows us to derive a bound of $mathbf{0}$ on the computational complexity required to learn uniformly enumerable families of equivalence structures. We also investigate variants of InfEx-learning, including learning from text (where the only information provided is which elements are related, and not which elements are not related) and finite learning (where the first actual conjecture of the learner has to be correct). Finally, we show how learning families of structures relates to learning classes of languages by mapping learning tasks for structures to equivalent learning tasks for languages.
rate research
Read More
We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, (relative) $Delta^0_alpha$ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of $Delta^0_alpha$ bi-embeddable categoricity and relative $Delta^0_alpha$ bi-embeddable categoricity coincide for equivalence structures for $alpha=1,2,3$. We also prove that computable equivalence structures have degree of bi-embeddable categoricity $mathbf{0},mathbf{0}$, or $mathbf{0}$. We obtain results on index sets of computable equivalence structure with respect to bi-embeddability.
A general theme of computable structure theory is to investigate when structures have copies of a given complexity $Gamma$. We discuss such problem for the case of equivalence structures and preorders. We show that there is a $Pi^0_1$ equivalence structure with no $Sigma^0_1$ copy, and in fact that the isomorphism types realized by the $Pi^0_1$ equivalence structures coincide with those realized by the $Delta^0_2$ equivalence structures. We also construct a $Sigma^0_1$ preorder with no $Pi^0_1$ copy.
Logicians and philosophers of science have proposed various formal criteria for theoretical equivalence. In this paper, we examine two such proposals: definitional equivalence and categorical equivalence. In order to show precisely how these two well-known criteria are related to one another, we investigate an intermediate criterion called Morita equivalence.
We combine computable structure theory and algorithmic learning theory to study learning of families of algebraic structures. Our main result is a model-theoretic characterization of the class $mathbf{InfEx}_{cong}$, consisting of the structures whose isomorphism types can be learned in the limit. We show that a family of structures $mathfrak{K}$ is $mathbf{InfEx}_{cong}$-learnable if and only if the structures from $mathfrak{K}$ can be distinguished in terms of their $Sigma^{mathrm{inf}}_2$-theories. We apply this characterization to familiar cases and we show the following: there is an infinite learnable family of distributive lattices; no pair of Boolean algebras is learnable; no infinite family of linear orders is learnable.
We study strong types and Galois groups in model theory from a topological and descriptive-set-theoretical point of view, leaning heavily on topological dynamical tools. More precisely, we give an abstract (not model theoretic) treatment of problems related to cardinality and Borel cardinality of strong types, quotients of definable groups and related objecets, generalising (and often improving) essentially all hitherto known results in this area. In particular, we show that under reasonable assumptions, strong type spaces are locally quotients of compact Polish groups. It follows that they are smooth if and only if they are type-definable, and that a quotient of a type-definable group by an analytic subgroup is either finite or of cardinality at least continuum.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
