45 results for Khoussainov, B, Report

Scott Families and Computably Categorical Structures
Khoussainov, B; Shore, R.A (199609)
Report
The University of Auckland LibraryEffective 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 (200003)
Report
The University of Auckland LibraryWe introduce the notion of update networks to model communication networks with infinite duration.In our formalization we use bipartite finite graphs and gametheoretic 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 (200003)
Report
The University of Auckland LibraryA 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 (199611)
Report
The University of Auckland LibraryEffective 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 LibraryMotivated 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 EhrenfeuchtFraïsselike 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 (200111)
Report
The University of Auckland LibraryWe 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 structuretheoretical setting.
View record details 
Finite State Strategies in One Player McNaughton Games
Khoussainov, B (200205)
Report
The University of Auckland LibraryIn 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
View record details
The University of Auckland Library 
Do the Zeros of the Riemann's ZetaFunction Form a Random Sequence?
Calude, C.S; Hertling, P.H; Khoussainov, B (199704)
Report
The University of Auckland LibraryThe 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 (199701)
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 (199612)
Report
The University of Auckland Library[no abstract available]
View record details 
Complexity of Computable Models
Goncharov, S.S; Khoussainov, B (200205)
Report
The University of Auckland Library[no abstract available]
View record details 
Solutions of the GoncharovMillar and Degree Spectra Problems in The Theory of Computable Models
Khoussainov, B; Shore, R.A (200003)
Report
The University of Auckland Library[no abstract available]
View record details 
Computable Isomorphism of Boolean Algebras with Operators
Khoussainov, B; Kowalski, T (200203)
Report
The University of Auckland LibraryOne 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 (199608)
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 (200301)
Report
The University of Auckland LibraryThis 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 (200003)
Report
The University of Auckland LibraryIn 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 (199807)
Report
The University of Auckland LibraryWe 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 (200412)
Report
The University of Auckland Library[no abstract available]
View record details 
Finite Automata and Isomorphism Types
Khoussainov, B; Rubin, S (200003)
Report
The University of Auckland LibraryIn this paper we report on some results about finite automata presentable structures, an area of research first proposed in a KhoussainovNerode 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