45 results for Khoussainov, B, Report

  • Scott Families and Computably Categorical Structures

    Khoussainov, B; Shore, R.A (1996-09)

    Report
    The University of Auckland Library

    Effective model theory is an area of logic that analyzes the effective content of the typical notions and results of model theory and universal algebra. Typical notions in model theory and universal algebra are languages and structures, theories and models, models and their submodels, automorphisms and isomorphisms, embeddings and elementary embeddings. In this paper languages, structures, and models are assumed to be countable. There are many ways to introduce considerations of effectiveness into the area of model theory or universal algebra. Here we will briefly explain considerations of effectiveness for theories and their models on the one hand, and for just structures on the other hand.

    View record details
  • Update Networks and Their Routing Strategies

    Dinneen, Michael; Khoussainov, B (2000-03)

    Report
    The University of Auckland Library

    We introduce the notion of update networks to model communication networks with infinite duration.In our formalization we use bipartite finite graphs and game-theoretic terminology as an underlying structure.F or these networks we exhibit a simple routing procedure to update information throughout the nodes of the network. We also introduce an hierarchy for the class of all update networks and discuss the complexity of some natural problems.

    View record details
  • Algebraic Constraints, Automata, and Regular Languages

    Khoussainov, B (2000-03)

    Report
    The University of Auckland Library

    A class of decision problems is Boolean if it is closed under the set{theoretic operations of union, intersection and complementation. The paper introduces new Boolean classes of decision problems based on algebraic constraints imposed on transitions of nite automata. We discuss issues related to speci cations of these classes from algebraic, computational and proof{theoretic points of view.

    View record details
  • Computably Categorical Structures and Expansions by Constants

    Cholak, P; Goncharov, S.S; Khoussainov, B; Shore, R.A (1996-11)

    Report
    The University of Auckland Library

    Effective model theory is the subject that analyzes the typical notions and results of model theory to determine their effective content and counterparts The subject has been developed both in the former Soviet Union and in the west with various names (recursive model theory, constructive model theory, etc.) and divergent terminology. (We use “effective model theory” as the most general and descriptive designation. Harizanov [6] is an excellent introduction to the subject as is Millar [14]. The basic subjects of model theory include languages, structures, theories, models and various types of maps between these objects. There are many ways to introduce considerations of effectiveness into the area. The two most prominent derive from starting, on the one hand, with the notion of a theory and its models or, on the other with just structures. --from Introduction

    View record details
  • Finite Nondeterministic Automata: Simulation and Minimality

    Calude, C.S; Calude, E; Khoussainov, B (1997 -09)

    Report
    The University of Auckland Library

    Motivated by recent applications of finite automata to theoretical physics, we study the minimization problem for nondeterministic automata (with outputs, but no initial states). We use Ehrenfeucht-Fraïsse-like games to model automata responses and simulations. The minimal automaton is constructed and, in contrast with the classical case, proved to be unique up to an isomorphism. Finally, we investigate the partial ordering induced by automata simulations. For example, we prove that, with respect to this ordering, the class of deterministic automata forms an ideal in the class of all automata.

    View record details
  • Uniformity in Computable Structure Theory

    Downey, R.G; Hirschfeldt, D.R; Khoussainov, B (2001-11)

    Report
    The University of Auckland Library

    We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, and discuss connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman on uniformity in a general computable structure-theoretical setting.

    View record details
  • Finite State Strategies in One Player McNaughton Games

    Khoussainov, B (2002-05)

    Report
    The University of Auckland Library

    In this paper we consider a class of infinite one player games played on finite graphs. Our main questions are the following: given a game, how efficient is it to find whether or not the player wins the game? If the player wins the game, then how much memory is needed to win the game? For a given number n, how does the underlying graph look like if the player has a winning strategy of memory size n?

    View record details
  • A Quest For Algorithmically Random Infinite Structures, II

    Khoussainov, B (2014)

    Report
    The University of Auckland Library

    View record details
  • Do the Zeros of the Riemann's Zeta-Function Form a Random Sequence?

    Calude, C.S; Hertling, P.H; Khoussainov, B (1997-04)

    Report
    The University of Auckland Library

    The aim of this note is to introduce the notion of random sequences of reals and to prove that the answer to the question in the title is negative, as anticipated by the informal discussion of Longpré and Kreinovich [15].

    View record details
  • Decidable Kripke Models of Intuitionistic Theories

    Ishihara, H; Khoussainov, B; Nerode, A (1997-01)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Computably Presentable Models of Theories with Few Models

    Khoussainov, B; Nies, A; Shore, R.A (1996-12)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Complexity of Computable Models

    Goncharov, S.S; Khoussainov, B (2002-05)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Solutions of the Goncharov-Millar and Degree Spectra Problems in The Theory of Computable Models

    Khoussainov, B; Shore, R.A (2000-03)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Computable Isomorphism of Boolean Algebras with Operators

    Khoussainov, B; Kowalski, T (2002-03)

    Report
    The University of Auckland Library

    One of the central topics in computable algebra and model theory is concerned with the study of computable isomorphisms. Classically, we do not distinguish between isomorphic structures, however, from computability point of view, isomorphic structures can differ quite dramatically. A typical example is provided by the linear order of type ω. It has two computable copies such that in one the successor function is computable, but it is not computable in the other. These are clearly classically isomorphic, but they are not computably isomorphic.

    View record details
  • Randomness, Computability, and Algebraic Specifications

    Khoussainov, B (1996-08)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Definability and Regularity in Automatic Presentations of Subsystems of Arithmetic

    Khoussainov, B; Rubin, S; Stephan, F (2003-01)

    Report
    The University of Auckland Library

    This paper is devoted to the study of the relationship between regularity and definability of relations in structures presented by finite automata. An emphasis is given to relations in fragments of arithmetic, in particular in (ω,≤), (ω, S), (ω, +) and some of their variants. A relation in a structure is intrinsically regular if it is regular in every automatic presentation of the structure. All definable relations in the first order logic with finite number of parameters are intrinsically regular. We investigate questions related to whether or not intrinsically regular relations are definable. For example, on the one hand, we show that the set M2 of all even numbers in every automatic presentation of (ω,≤) is intrinsically regular (but not definable). On the other, we show that there exists an automatic presentation of (ω, S) in which the set M2 is not regular. In particular, we show that a unary relation in (ω, S) is intrinsically regular if and only if it is definable.

    View record details
  • On Computable Theoretic Properties of Structures and Their Cartesian Products

    Khoussainov, B (2000-03)

    Report
    The University of Auckland Library

    In this paper we show that for any set X C ω there exists a structure A that has no presentation computable in X such that A2 has a computable presentation. We also show that there exists a structure A with infinitely many computable isomorphism types such that A2 has exactly one computable isomorphism type.

    View record details
  • Computable Kripke Models and Intermediate Logics

    Ishihara, H; Khoussainov, B; Nerode, A (1998-07)

    Report
    The University of Auckland Library

    We introduce effectiveness considerations into model theory of intuitionistic logic. We investigate effectiveness of completeness (by Kripke) results for intermediate logics such as for example, intuitionistic logic, classical logic, constant domain logic, directed frames logic, Dummett's logic, etc.

    View record details
  • Abstracts of the Workshop on Automata, Structures and Logic

    Khoussainov, B (2004-12)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Finite Automata and Isomorphism Types

    Khoussainov, B; Rubin, S (2000-03)

    Report
    The University of Auckland Library

    In this paper we report on some results about finite automata presentable structures, an area of research first proposed in a Khoussainov-Nerode paper in 1995 [1]. The topic of automata presentable structures is new, under development and is on the edge of interactions between automata theory, (universal) algebra, model theory and complexity theory.

    View record details