Browsing by Author "SEMUKHIN, Pavel"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    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.
  • No Thumbnail Available
    Item
    Uncountable Automatic Classes and Learning
    (2009-02-02T08:30:27Z) JAIN, Sanjay; LUO, Qinglong; SEMUKHIN, Pavel; STEPHAN, Frank
    In this paper we consider uncountable classes recognizable by omega-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language L from the class plus an omega-index alpha and outputs a sequence of omega-automata such that all but finitely many of these omega-automata accept the index alpha if and only if alpha is an index for L.