Browsing by Author "MARTIN, Eric"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    Item
    Robust learning of automatic classes of languages
    (2010-04-22T05:28:14Z) JAIN, Sanjay; MARTIN, Eric; STEPHAN, Frank
    This paper adapts and investigates the paradigm of robust learning, originally defined in the framework of inductive inference of classes of recursive functions, to learning languages from positive data. Robustness is a very desirable property, as it captures a form of invariance of learnability under admissible transformations of the object of study.The classes of languages of interest are automatic, that is, recognisable by finite automata. A class of first-order definable operators - called translators - is introduced as natural transformations that preserve automaticity of a class of languages and the inclusion relationships between languages in the class. For many learning criteria, we provide a characterization of the classes of languages all of whose translations are learnable under that criterion. The learning criteria have been chosen from the literature on both explanatory learning and query learning, and include consistent and conservative learning, strong-monotonic learning, strong-monotonic consistent learning, finite learning, learning from subset queries, learning from superset queries and learning from membership queries.