اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدLearnability and Positive Equivalence Relations
96
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Prior work of Gavryushkin, Khoussainov, Jain and Stephan investigated what algebraic structures can be realised in worlds given by a positive (= recursively enumerable) equivalence relation which partitions the natural numbers into infinitely many equivalence classes. The present work investigates the infinite one-one numbered recursively enumerable (r.e.) families realised by such relations and asks how the choice of the equivalence relation impacts the learnability properties of these classes when studying learnability in the limit from positive examples, also known as learning from text. For all choices of such positive equivalence relations, for each of the following entries, there are one-one numbered r.e. families which satisfy it: (a) they are behaviourally correctly learnable but not vacillatorily learnable; (b) they are explanatorily learnable but not confidently learnable; (c) they are not behaviourally correctly learnable. Furthermore, there is a positive equivalence relation which enforces that (d) every vacillatorily learnable one-one numbered family of languages closed under this equivalence relation is already explanatorily learnable and cannot be confidently learnable.
قيم البحث
اقرأ أيضاً
We introduce notions of continuous orbit equivalence and strong (respective, weak) continuous orbit equivalence for automorphism systems of {e}tale equivalence relations, and characterize them in terms of the semi-direct product groupoids, as well as
their reduced groupoid $C^*$-algebras with canonical Cartan subalgebras. In particular, we study topological rigidity of expansive automorphism actions on compact (connected) metrizable groups.
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.
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations $R$ and $S$ on natural numbers, $R$ is computably reducible to $
S$ if there is a computable function $f colon omega to omega$ that induces an injective map from $R$-equivalence classes to $S$-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore $mathbf{Peq}$, the degree structure generated by primitive recursive reducibility on punctual equivalence relations (i.e., primitive recursive equivalence relations with domain $omega$). In contrast with all other known degree structures on equivalence relations, we show that $mathbf{Peq}$ has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of $mathbf{Peq}$, proving, e.g., that the structure is neither rigid nor homogeneous.
This note studies the existence of quotients by finite set theoretic equivalence relations. May 18: Substantial revisions with a new appendix by C. Raicu
Intruders can infer properties of a system by measuring the time it takes for the system to respond to some request of a given protocol, that is, by exploiting time side channels. These properties may help intruders distinguish whether a system is a
honeypot or concrete system helping him avoid defense mechanisms, or track a user among others violating his privacy. Observational equivalence is the technical machinery used for verifying whether two systems are distinguishable. Moreover, efficient symbolic methods have been developed for automating the check of observational equivalence of systems. This paper introduces a novel definition of timed observational equivalence which also distinguishes systems according to their time side channels. Moreover, as our definition uses symbolic time constraints, it can be automated by using SMT-solvers.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
