45 results for Khoussainov, B, Report

  • Degree-Theoretic Aspects of Computably Enumerable Reals

    Calude, C.S; Coles, R.J; Hertling, P.H; Khoussainov, B (1998-09)

    Report
    The University of Auckland Library

    A real α is computable if its left cut, L(α); is computable. If (qi)i is a computable sequence of rationals computably converging to α, then {qi}, the corresponding set, is always computable. A computably enumerable (c.e.) real is a real which is the limit of an increasing computable sequence of rationals, and has a left cut which is c.e. We study the Turing degrees of representations of c.e. reals, that is the degrees of increasing computable sequences converging to α. For example, every representation A of α is Turing reducible to L(α). Every noncomputable c.e. real has both a computable and noncomputable representation. In fact, the representations of noncomputable c.e. re- als are dense in the c.e. Turing degrees, and yet not every c.e. Turing degree below degT L(α) necessarily contains a representation of α.

    View record details
  • Games on Graphs: Automata, Structure, and Complexity

    Khoussainov, B; Kowalski, T (2003-01)

    Report
    The University of Auckland Library

    McNaughton in his known paper [7], motivated by the work of Gurevich and Harrington [4], introduced a class of games played on finite graphs. In his paper McNaughton proves that winners in his games have winning strategies that can be implemented by finite state automata. McNaughton games have attracted attention of many experts in the area, partly because the games have close relationship with automata theory, the study of reactive systems, and logic (see, for instance, [12] and [11]). McNaughton games can also be used to develop game-theoretical approach for many important concepts in computer science such as models for concurrency, communication networks, and update networks, and provide natural examples of computational problems. For example, Nerode, Remmel and Yakhnis in a series of papers (e.g., [8], [9]) developed foundations of concurrent programming in which finite state strategies of McNaughton games are identified with distributed concurrent programs. -- from Introduction

    View record details
  • Deterministic Automata: Simulation, Universality and Minimality

    Calude, C; Calude, E; Khoussainov, B (1996-12)

    Report
    The University of Auckland Library

    Finite automata have been recently used as alternative, discrete models in theoretical physics, especially in problems related to the dichotomy between endophysical/intrinsic and exophysical/ extrinsic perception (see, for instance [15, 18, 16, 7, 17, 4]). These studies deal with Moore experiments; the main result states that it is impossible to determine the initial state of an automaton, and, consequently, a discrete model of Heisenberg uncertainty has been suggested. For this aim the classical theory of finite automata{which considers automata with initial states{is not adequate, and a new approach is necessary. A study of finite deterministic automata without initial states is exactly the aim of this paper. We will define and investigate the complexity of various types of simulations between automata. Minimal automata will be constructed and proven to be unique up to an isomorphism. We will build our results on an extension of Myhill-Nerode technique; all constructions will make use of “automata responses" to simple experiments only, i.e., no information about the internal machinery will be considered available.

    View record details
  • Open Problems in the Theory of Constructive Algebraic Systems

    Goncharov, S.S; Khoussainov, B (2000-03)

    Report
    The University of Auckland Library

    In this paper we concentrate on open problems in two directions in the development of the theory of constructive algebraic systems. The first direction deals with universal algebras whose positive open diagrams can be computably enumerated. These algebras are called positive algebras. Here we emphasize the interplay between universal algebra and computability theory. We propose a systematic study of positive algebras as a new direction in the development of the theory of constructive algebraic systems. The second direction concerns the traditional topics in constructive model theory. First we propose the study of constructive models of theories with few models such as countably categorical theories, uncountably categorical theories, and Ehrenfeucht theories. Next, we propose the study of computable isomorphisms and computable dimensions of such models. We also discuss issues related to the computability-theoretic complexity of relations in constructive algebraic systems.

    View record details
  • Deciding Parity Games in Quasipolynomial Time

    Calude, CS; Jain, S; Khoussainov, B; Li, W; Stephan, F (2016)

    Report
    The University of Auckland Library

    It is shown that the parity game can be solved in quasipolynomial time. The parameterised parity game (with n nodes and m distinct values) is proven to be in the class of fixed parameter tractable (FPT) problems (when parameterised over m).

    View record details
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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