45 results for Khoussainov, B, Report

  • 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
  • Reducibilities Among Equivalence Relations Induced by Recursively Enumerable Structures

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

    Report
    The University of Auckland Library

    In this paper we investigate the dependence of recursively enumerable structures on the equality relation which is fixed to a specific r.e. equivalence relation. We compare r.e. equivalence relations on the natural numbers with respect to the amount of structures they permit to represent from a given class of structures such as algebras, permutations and linear orders. In particular, we show that for various types of structures represented, there are minimal and maximal elements.

    View record details
  • Update Games and Update Networks

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

    Report
    The University of Auckland Library

    In this paper we model infinite processes with finite configurations as infinite games over finite graphs. We investigate those games, called update games, in which each configuration occurs an infinite number of times during a two-person play. We also present an efficient polynomial-time algorithm (and partial characterization) for deciding if a graph is an update network.

    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
  • On Isomorphism Invariants of Some Automatic Structures

    Ishihara, H; Khoussainov, B; Rubin, S (2002-01)

    Report
    The University of Auckland Library

    In this paper we study structures defined by finite automata, called automatic structures. We provide a method that reduces the study of automatic structures to the study of automatic graphs. We investigate isomorphism invariants of automatic structures with an emphasis to equivalence relation structures, linearly ordered sets, and permutation structures.

    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
  • Games Played on Finite Graphs and Temporal Logic

    Khoussainov, B (2002-01)

    Report
    The University of Auckland Library

    Our aim is to study reductive finite state systems (e.g. communication networks, banking systems, airtraffic control systems) by means of game-theoretic methods. A reactive system acts upon the inputs from environment by changing its states. The goal of the system is to satisfy given specifications no matter how environment behaves. We model this situation using games played on finite graphs first introduced by McNaughton [6].

    View record details
  • On Game-Theoretic Models of Networks

    Bodlaender, H.L; Dinneen, Michael; Khoussainov, B (2001-04)

    Report
    The University of Auckland Library

    In this paper, we study the complexity of deciding which player has a winning strategy in certain types of McNaughton games. These graph games can be used as models for computational problems and processes of infinite duration. We consider the cases (1) where the first player wins when vertices in a specified set are visited infinitely often and vertices in another specified set are visited finitely often, (2) where the first player wins when exactly those vertices in one of a number of specified disjoint sets are visited infinitely often, and (3) a generalization of these first two cases. We give polynomial time algorithms to determine which player has a winning strategy in each of the games considered.

    View record details
  • Recursively Enumerable Reals and Chaitin Omega Numbers

    Calude, C.S; Hertling, P.H; Khoussainov, B; Wang, Y (1997-10)

    Report
    The University of Auckland Library

    A real α is called recursively enumerable if it can be approximated by an increasing, recursive sequence of rationals. The halting probability of a universal self- delimiting Turing machine (Chaitin's Ω number, [10]) is a random r.e. real. Solovay's [25] Ω-like reals are also random r.e. reals. Solovay showed that any Chaitin Ω number is Ω-like. In this paper we show that the converse implication is true as well: any Ω-like real in the unit interval is the halting probability of a universal self-delimiting Turing machine. Following Solovay [25] and Chaitin [11] we say that an r.e. real α dominates an r.e. real β if from a good approximation of α from below one can compute a good approximation of β from below. We shall study this relation and characterize it in terms of relations between r.e. sets. Ω-like numbers are the maximal r.e. real numbers with respect to this order, that is, from a good approximation to an Ω-like real one can compute a good approximation for every r.e. real. This property shows the strength of Ω for approximation purposes. However, the situation is radically different if one wishes to compute digits of the binary expansion of an r.e. real: one cannot compute with a total recursive function the first n digits of the r.e. real 0:¬xK (the characteristic sequence of the halting problem) from the first g(n) digits of Ω, for any total recursive function g.

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

    Khoussainov, B (2014)

    Report
    The University of Auckland Library

    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
  • 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
  • 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
  • Complexity of Computable Models

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

    Report
    The University of Auckland Library

    [no abstract available]

    View record details