The algebraic uniqueness of the addition of natural numbers.
The arithmetic and turing degrees are not elementary equivalent.
The Backward and Forward Summation of Infinite Series of Isols.
The boundedness principle in ordinal recursion
The C k Space
In this article, we formalize continuous differentiability of realvalued functions on n-dimensional real normed linear spaces. Next, we give a definition of the Ck space according to [23].
The category of recursive functions
The communication hierarchy of time and space bounded parallel machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The Communication Hierarchy of Time and Space Bounded Parallel Machines
We describe the communicating alternating machines and their simulation. We show that, in the case of communicating alternating machines which are bounded, simultaneously, by polynomial time and logarithmic space, the use of three communication levels instead of two does not increase computational power of communicating alternating machines. This resolves an open problem [2] concerning the exact position of machines with three communication levels in the hierarchy.
The complexity of retina operators.
The complexity of uniform distribution
The computability potential scale of all finite algebras.
The concept of a binary relation over partial enumerated sets.
The conjugacy problem for groups, and Higman embeddings.
The connection between the fundamental groupoid and a unification algorithm for syntactil algebras (extended abstract)
The degree spectra of definable relations on Boolean algebras.
The difference and truth-table hierarchies for NP
The effective Borel hierarchy
Let K be a subclass of Mod() which is closed under isomorphism. Vaught showed that K is (respectively, ) in the Borel hierarchy iff K is axiomatized by an infinitary (respectively, ) sentence. We prove a generalization of Vaught’s theorem for the effective Borel hierarchy, i.e. the Borel sets formed by union and complementation over c.e. sets. This result says that we can axiomatize an effective or effective Borel set with a computable infinitary sentence of the same complexity. This result...
The finite levels of the hierarchy of effective R-sets
The first order properties of Dedekind finite integers
The helping hierarchy
Schöning [14] introduced a notion of helping and suggested the study of the class of the languages that can be helped by oracles in a given class . Later, Ko [12], in order to study the connections between helping and “witness searching”, introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call which contains all the self-helping classes. We introduce the Helping hierarchy whose levels are...