45 results for Khoussainov, B, Report

  • Some Thoughts On Automatic Structures

    Khoussainov, B; Rubin, S (2002-05)

    Report
    The University of Auckland Library

    Our aim in writing this paper is twofold. On the one hand, we present the theory of automatic structures from the points of view of model theory, algebra, complexity theory, and automata theory. On the other hand, we survey basic results and present possible directions for future research in the area. --from Introduction

    View record details
  • Effective Model Theory: The Number of Models and Their Complexity

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

    Report
    The University of Auckland Library

    Effective model theory studies model theoretic notions with an eye towards issues of computability and effectiveness. We consider two possible starting points. If the basic objects are taken to be theories, then the appropriate effective version investigates decidable theories (the set of theorems is computable) and decidable structures (ones with decidable theories). If the objects of initial interest are typical mathematical structures, then the starting point is computable structures. We present an introduction to both of these aspects of effective model theory organized roughly around the themes of the number and types of models of theories with particular attention to categoricity (as either a hypothesis or a conclusion) and the analysis of various computability issues in families of models.

    View record details
  • On Complexity of Computatable $\aleph_1$--Categorical Models

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

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Automatic linear orders and trees (Revised)

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

    Report
    The University of Auckland Library

    We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.

    View record details
  • Semiautomatic Structures

    Jain, S; Khoussainov, B; Stephan, F; Teng, D; Zou, S (2014)

    Report
    The University of Auckland Library

    Semiautomatic structures generalise automatic structures in the sense that for some of the relations and functions in the structure one only requires the derived relations and structures are automatic when all but one input are filled with constants. One can also permit that this applies to equality in the structure so that only the sets of representatives equal to a given element of the structure are regular while equality itself is not an automatic relation on the domain of representatives. It is shown that one can find semiautomatic representations for the field of rationals and also for finite algebraic field extensions of it. Furthermore, one can show that infinite algebraic extensions of finite fields have semiautomatic representations in which the addition and equality are both automatic. Further prominent examples of semiautomatic structures are term algebras, any relational structure over a countable domain with a countable signature and any permutation algebra with a countable domain. Furthermore, examples of structures which fail to be semiautomatic are provided.

    View record details
  • Graphs Realised by R.E. Equivalence Relations

    Gavruskin, A; Jain, S; Khoussainov, B; Stephan, F (2014)

    Report
    The University of Auckland Library

    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.

    View record details
  • Automata with Equational Constraints

    Dinneen, Michael; Khoussainov, B (1999-08)

    Report
    The University of Auckland Library

    We introduce the concept of nite automata with algebraic constraints. We show that the languages accepted by these automata are closed under the Boolean operations. We give efficient polynomial-time algorithms for some decision problems related to these automata and their languages, including sufficient conditions for when we can determinize automata in polynomial time.

    View record details
  • Algebraic Constraints, Automata, and Regular Languages (Revised)

    Khoussainov, B (2001-11)

    Report
    The University of Auckland Library

    The paper studies classes of regular languages based on algebraic constraints imposed on transitions of automata and discusses issue related to specifications of these classes from algebraic, computational and logical points of view.

    View record details
  • 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
  • A Quest For Algorithmically Random Infinite Structures, II

    Khoussainov, B (2014)

    Report
    The University of Auckland Library

    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
  • 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
  • Degree Spectra and Computable Dimensions in Algebraic Structures

    Hirschfeldt, D.R; Khoussainov, B; Shore, R.A; Slinko, A.M (2001-10)

    Report
    The University of Auckland Library

    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
  • 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
  • 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