DSpace Angular :: Browsing by Author "STEPHAN, Frank"

Browsing by Author "STEPHAN, Frank"

Now showing 1 - 20 of 36

Absolute versus probabilistic classification in a logical setting
(2006-03-22T01:23:33Z) JAIN, Sanjay; MARTIN, Eric; STEPHAN, Frank
Given a set W of logical structures, or possible worlds, a set of logical formulas called possible data and a logical formula phi, we consider the classification problem of determining in the limit and almost always correctly whether a possible world M in W satisfies phi, from a complete enumeration of the possible data that are true in M. One interpretation of almost always correctly is that the classification might be wrong on a set of possible worlds of measure 0, with respect to some natural probability distribution over the set of possible worlds. Another interpretation is that the classifier is only required to classify a set W' of possible worlds of measure 1, without having to produce any claim in the limit on the truth of phi in the members of W which are not in W'. We compare these notions with absolute classification of W with respect to a formula that is almost always equivalent to phi in W, hence investigate whether the set of possible worlds on which the classification is correct is definable. We mainly work with the probability distribution that corresponds to the standard measure on the Cantor space, but we also consider an alternative probability distribution proposed by Solomonoff and contrast it with the former. Finally, in the spirit of the kind of computations considered in Logic programming, we address the issue of computing almost correctly in the limit witnesses to leading existentially quantified variables in existential formulas.
Applications of Kolmogorov Complexity to Computable Model Theory
(2006-09-07T06:46:20Z) KHOUSSAINOV, Bakhadyr; SEMUKHIN, Pavel; STEPHAN, Frank
In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not countably categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of a uncountably categorical but not countably categorical saturated Sigma-0-1-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an uncountably categorical but not countably categorical theory whose only non-computable model is the prime one.
The Complexity of the Set of Nonrandom Numbers
(2007-02-28) STEPHAN, Frank
Let C and H denote the plain and prefix-free Kolmogorov complexity, respectively. Then the sets NRC of nonrandom numbers with respect to C has neither a maximal nor an r-maximal superset. The set of NRH of nonrandom numbers with respect to H has an r-maximal but no maximal superset. Thus the lattices of recursively enumerable supersets (modulo finite sets) of NRC and NRH are not isomorphic. Further investigations deal with the related set NRW of all numbers x which are the maximum of some r.e. set with an index e < x. Friedman originally asked whether NRW is Turing equivalent to K and Davie provided a positive answer for many acceptable numberings. Later Teutsch asked the related question whether one can choose the underlying acceptable numbering such that NRW is either an r.e. or co-r.e. set. A negative answer is provided to this question and the position of NRW in the difference-hierarchy is provided: one can choose the underlying numbering such that NRW is a co-2-r.e. set but NRW is never a 2-r.e. set. Furthermore, if the underlying numbering is a Kolmogorov numbering, then NRW is an omega-r.e. set but not an n-r.e. set for any natural number n.
Computable Categoricity and the Ershov Hierarchy
(2007-08-31) KHOUSSAINOV, Bakhadyr; STEPHAN, Frank; YANG, Yue
In this paper, the notions of F[alpha]-categorical and G[alpha]-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the alpha-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G[2]-categorical; in the latter case it is not F[alpha]-categorical for any recursive ordinal alpha.
Confident and Consistent Partial Learning of Recursive Functions
(2014-07-10) GAO, Ziyuan; STEPHAN, Frank
Partial learning is a criterion where the learner in nitely often outputs one correct conjecture while every other hypothesis is issued only nitely often. This paper addresses two variants of partial learning in the setting of inductive inference of functions: rst, con dent partial learning requires that the learner also on those functions which it does not learn, singles out exactly one hypothesis which is output in nitely often; second, essentially class consistent partial learning is partial learning with the additional constraint that on the functions to be learnt, almost all hypothe- ses issued are consistent with all the data seen so far. The results of the present work are that con dent partial learning is more general than explanatory learning, incom- parable with behaviourally correct learning and closed under union; essentially class consistent partial learning is more general than behaviourally correct learning and incomparable with con dent partial learning. Furthermore, it is investigated which oracles permit to learn all recursive functions under these criteria: for con dent par- tial learning, some non-high oracles are omniscient; for essentially class consistent partial learning, all PA-complete and all oracles of hyperimmune Turing degree are omniscient.
The Discrete Time Behaviour of Restricted Linear Hybrid Automata
(2008-12-15T01:59:32Z) AGRAWAL, Manindra; STEPHAN, Frank; THIAGARAJAN, P. S.; YANG, Shaofa
We summarize results from [2, 3, 1] on the discrete time behaviour of a class of restricted linear hybrid automata. Specifically, we show the regularity of the discrete time behaviour of hybrid automata in which the rates of continuous vari- ables are governed by linear operators in a diagonal form and in which the values of the continuous variables can be observed only with finite precision. Crucially, we do not demand—as is usually done—that the values of the continuous vari- ables be reset during mode changes. We can cope with polynomial guards and we can tolerate bounded delays both in sampling the values of the continuous variables and in effecting changes in their rates required by mode switchings. We also show that if the rates are governed by diagonalizable linear operators with rational eigenvalues and there is no delay in effecting rate changes, the discrete time behaviour of the hybrid automaton is recursive. However, the control state reachability problem in this setting is undecidable.
Extractors and Constructive Dimensions of Weak Truth-Table Degrees
(2007-01-17T08:08:52Z) BIENVENU, Laurent; DOTY, David; STEPHAN, Frank
This paper examines the constructive Hausdorff and packing dimensions of weak truth-table degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dimH(S) and constructive packing dimension dimP(S)is weak truth-table equivalent to a sequence R with dimH(R)> dimH(S)/dimP(S)- Îµ, for arbitrary Îµ > 0. Furthermore, if dimP(S) > 0, then dimP(R) > 1 - Îµ. The reduction thus serves as a randomness extractor that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of wtt degrees (and, by extension, Turing degrees). A lower bound of dimH(S)/dimP(S) is shown to hold for the wtt degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of wtt degrees. It is also shown that, for any regular sequence S (that is, dimH(S) = dimP(S)) such that dimH(S) > 0, the wtt degree of S has Hausdorff and packing dimension 1.
Hierarchies of Randomness Tests
(2006-02-10T06:54:28Z) REIMANN, Jan; STEPHAN, Frank
It is well known that Martin-Loef randomness can be characterized by a number of equivalent test concepts, based either on effective nullsets (Martin-Loef and Solovay tests) or on prefix-free Kolmogorov complexity (lower and upper entropy). These equivalences are not preserved as regards the partial randomness notions induced by effective Hausdorff measures or partial incompressibility. Tadaki as well as Calude, Staiger and Terwijn studied several concepts of partial randomness, but for some of them the exact relations remained unclear. In this paper we will show that they form a proper hierarchy of randomness notions, namely for any rho where rho(x) is 2 to the power of -|x|s and s is a rational number satisfying 0
Immunity and Hyperimmunity for Generalized Random Strings
(2007-05-17T09:35:39Z) STEPHAN, Frank; TEUTSCH, Jason
We introduce generalizations of the Kolmogorov random strings, called minimal index sets. The set of Kolmogorov random strings are known to be immune but not hyperimmune. In contrast, minimal index sets are not only immune but also immune against high levels of the arithmetic hierarchy. We give optimal immunity results with respect to the arithmetic hierarchy and we consider the set MIN* as an intuitive counter-example. Of particular note here are the fact that there are three minimal index sets located in Pi-3 but not in Sigma-3 with distinct immunities and that certain immunity properties depend on the choice of Goedel numbering. We show that minimal index sets are not hyperimmune. As a consequence of this fact, we are able to construct a set which neither contains nor is disjoint from any arithmetic set, yet it is majorized by a recursive function and contains a minimal index set. Lastly, we present generalizations of the Kolmogorov random strings which, unlike the more familiar random strings, need not be Turing complete.
Implementing Fragments of ZFC within an r.e. Universe
(2009-06-30) MARTIN, Eric; PONG, Wai Yan; STEPHAN, Frank
Rabin showed that there is no r.e. model of the axioms of Zermelo and Fraenkel of set theory. In the present work, it is investigated to which extent natural models of a sufficiently rich fragment of set theory exist. Such models, called Friedberg models in the present work, are built as a class of subsets of the natural numbers, together with the element-relation given as x is in y if and only if x is in the set y-th r.e. set from a given Friedberg numbering of all r.e. sets of natural numbers. The y-th member of this numbering is then considered to be a set in the given model iff the downward closure of the induced element-ordering from y is well-founded. For each axiom and basic property of set theory, it is shown whether or not that axiom or property holds in such a model. Comprehension and replacement need to be properly adapted, as not all functions and objects definable using first-order logic exist in the model. The validity of the power set axiom, in an adequate formulation, depends on the model chosen. The other axioms hold in every Friedberg model. Furthermore, it is shown that there is a least Friedberg model which contains exactly those sets from the von Neumann universe which exist in all Friedberg models while there is no greatest Friedberg model. The complexity of the theory of a Friedberg model depends much on the model and ranges from the omega-jump of the halting problem to the omega-jump of a Pi-1-1-complete set.
Index Sets and Universal Numberings
(2009-03-17T01:51:08Z) JAIN, Sanjay; STEPHAN, Frank; TEUTSCH, Jason
This paper studies the Turing degrees of various properties defined for universal numberings, that is, for numberings which list all partial-recursive functions. In particular properties relating to the domain of the corresponding functions are investigated like the set DEQ of all pairs of indices of functions with the same domain, the set DMIN of all minimal indices of sets and DMIN* of all indices which are minimal with respect to equality of the domain modulo finitely many differences. A partial solution to a question of Schaefer is obtained by showing that for every universal numbering with the Kolmogorov property, the set DMIN* is Turing equivalent to the double jump of the halting problem. Furthermore, it is shown that the join of DEQ and the halting problem is Turing equivalent to the jump of the halting problem and that there are numberings for which DEQ itself has 1-generic Turing degree.
Invertible Classes
(2005-12-08T07:17:18Z) JAIN, Sanjay; NESSEL, Jochen; STEPHAN, Frank
In this paper we consider how and when general recursive operators can be inverted. This is motivated by the fact that in many situations in real life, one is interested in finding causes from the results. We also introduce the notion of coverability, which allows us to get a simpler representative enumeration of operators which satisfy some nice properties. We consider four notions of inversion --- strong inversion, inversion, weak inversion and bounded weak inversion --- and show that these separate. We also considered three notions of enumerations of operators to cover a class in the sense that the behaviour of every general recursive operator on the class is met. These three notions are strong covering, covering and weak covering --- where an acceptable numbering weakly covers all classes. We seaprate the induced notions of coverability. We also consider some special classes such as recursively enumerable classes and periodic classes. We show some interesting properties such as these classes are strongly invertible. We also show that some recursively enumerable classes, but not the class of periodic functions, are coverable.
Learnability of Automatic Classes
(2009-01-29T02:57:33Z) JAIN, Sanjay; LUO, Qinglong; STEPHAN, Frank
The present work initiates the study of the learnability of automatic indexable classes which are classes of regular languages of a certain form. It is characterised which of these classes are explanatorily learnable. Furthermore, the notion of an automatic iterative learner is introduced and it is studied for automatic classes whether they are learnable by an automatic iterative learner, learnable by an automatic iterative learner with additional long-term memory or unlearnable by such a learner. The dependence of the learnability on the indexing is also investigated. This work brings together the fields of inductive inference and automatic structures.
Learning in Friedberg Numberings
(2007-11-14) JAIN, Sanjay; STEPHAN, Frank
In this paper we consider learnability in some special numberings, such as Friedberg numberings, which contain all the recursively enumerable languages, but have simpler grammar equivalence problem compared to acceptable numberings. We show that every explanatorily learnable class can be learnt in some Friedberg numbering. However, such a result does not hold for behaviourally correct learning or finite learning. One can also show that some Friedberg numberings are so restrictive that all classes which can be explanatorily learnt in such Friedberg numberings have only finitely many infinite languages. We also study similar questions for several properties of learners such as consistency, conservativeness, prudence, iterativeness and non U-shaped learning. Besides Friedberg numberings, we also consider the above problems for programming systems with $K$-recursive grammar equivalence problem.
Lowness for Weakly 1-Generic and Kurtz-Random
(2005-12-20) STEPHAN, Frank; LIANG, Yu
It is shown that a set is low for weakly 1-generic iff it has neither dnr nor hyperimmune Turing degree. As this notion is more general than being recursively traceable, this answers negatively a recent question on the characterization of these sets. Furthermore, it is shown that every set which is low for weakly 1-generic is also low for Kurtz-random. In addition to this, it is shown that a set satisfies the notion ``low for diagonally non-recursive'' as introduced by Kjos-Hanssen and Nies iff it is recursive.
Lowness Properties and Approximations of the Jump
(2005-11-10) FIGUEIRA, Santiago; NIES, Andre; STEPHAN, Frank
We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set T_e of possible values for the jump J^A(e) and the number of values enumerated is at most h(e). A' is well-approximable if can be effectively approximated with less than h(x) changes at input x, for each order function h. We prove that there is a strongly jump-traceable set which is not computable, and that if A' is well-approximable then A is strongly jump-traceable. For r.e. sets, the converse holds as well. We characterize jump-traceability and the corresponding strong variant in terms of Kolmogorov complexity, and we investigate other properties of these lowness ...
Memory-Limited U-Shaped Learning
(2005-12-02T09:37:07Z) CARLUCCI, Lorenzo; CASE, John; JAIN, Sanjay; STEPHAN, Frank
U-shaped learning is a learning behaviour in which the learner first learns something, then unlearns it and finally relearns it. Such a behaviour, observed by psychologists, for example, in the learning of past-tenses of English verbs, has been widely discussed among psychologists and cognitive scientists as a fundamental example of the non-monotonicity of learning. Previous theory literature has studied whether or not U-shaped learning, in the context of Gold's formal model of learning languages from positive data, is necessary for learning some tasks. It is clear that human learning involves memory limitations. In the present paper we consider, then, this question of the necessity of U-shaped learning for some learning models featuring memory limitations. Our results show that the question of the necessity of U-shaped learning in this memory-limited setting depends on delicate tradeoffs between the learner's ability to remember its own previous conjecture, to store some values in its long-term memory, to make queries about whether or not items occur in previously seen data and on the learner's choice of hypothesis space.
A minimal rK-degree
(2005-11-25T01:20:54Z) RAICHEV, Alexander; STEPHAN, Frank
We construct a minimal rK-degree, continuum many, in fact. We also show that every minimal sequence, that is, a sequence with minimal rK-degree, must have very low descriptional complexity, that every minimal sequence is rK-reducible to a random sequence and that there is a random sequence with no minimal sequence rK-reducible to it.
Mitotic Classes
(2007-08-21T03:16:07Z) JAIN, Sanjay; STEPHAN, Frank
For the natural notion of splitting classes into two disjoint subclasses via a recursive classifier working on texts, the question is addressed how these splittings can look in the case of learnable classes. Here the strength of the classes is compared using the strong and weak reducibility from intrinsic complexity. It is shown that, for explanatorily learnable classes, the complete classes are also mitotic with respect to weak and strong reducibility, respectively. But there is a weak complete class which cannot be split into two classes which are of the same complexity with respect to strong reducibility. It is shown that for complete classes for behaviourally correct learning, one half of each splitting is complete for this learning notion as well. Furthermore, it is shown that explanatorily learnable and recursively enumerable classes always have a splitting into two incomparable classes; this gives an inductive inference counterpart of Sacks Splitting Theorem from recursion theory.
Numberings Optimal for Learning
(2008-08-25) JAIN, Sanjay; STEPHAN, Frank
This paper extends previous studies on learnability in non-acceptable numberings by considering the question: for which criteria which numberings are optimal, that is, for which numberings it holds that one can learn every learnable class using the given numbering as hypothesis space. Furthermore an effective version of optimality is studied as well. It is shown that the effectively optimal numberings for finite learning are just the acceptable numberings. In contrast to this, there are non-acceptable numberings which are optimal for finite learning and effectively optimal for explanatory, vacillatory and behaviourally correct learning. The numberings effectively optimal for explanatory learning are the K-acceptable numberings. A similar characterization is obtained for the numberings which are effectively optimal for vacillatory learning. Furthermore, it is studied which numberings are optimal for one and not for another criterion: among the criteria of finite, explanatory, vacillatory and behaviourally correct learning all separations can be obtained; however every numbering which is optimal for explanatory learning is also optimal for consistent learning.

Browsing by Author "STEPHAN, Frank"

Results Per Page

Sort Options