A selection property of the boolean -calculus and some of its applications
A simple detailed proof for Goedel's incompleteness theorem
A survey of hereditary properties of graphs
In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.
A survey on real structural complexity theory.
A Turing machine oracle hierarchy. I.
A Turing machine oracle hierarchy. II.
A Turing machine space hierarchy
A -set of natural numbers which is not enumerable by natural numbers.
About the admissible predicates on admissible sets.
About the domino problem in the hyperbolic plane from an algorithmic point of view
This paper is a contribution to the general tiling problem for the hyperbolic plane. It is an intermediary result between the result obtained by R. Robinson [Invent. Math.44 (1978) 259–264] and the conjecture that the problem is undecidable.
Abstract -expansions and ultimately periodic representations
For abstract numeration systems built on exponential regular languages (including those coming from substitutions), we show that the set of real numbers having an ultimately periodic representation is if the dominating eigenvalue of the automaton accepting the language is a Pisot number. Moreover, if is neither a Pisot nor a Salem number, then there exist points in which do not have any ultimately periodic representation.
Alan Mathison Turing – život a dílo
Aleatoreidad e inmunidad.
By introducing the concept of randomness through notions of recursion theory, the set of the random numbers is effectively immune. The proof of this well-known result makes an essential use of the recursion theorem. In this paper, randomness is introduced starting from the more common notion of definability in Robinson's arithmetic and the same result is obtained using an extension of the fixed-point theorem, which we prove at the end of the paper. Finally we define a recursive function dominating...
Algebra grammars
Algebraic caractérisations of NTIME and NTIME
Algorithmische Probleme bei Einrelatorgruppen und ihre Komplexität.
Algorithmization of algebras and relational structures
An algebraic treatment of flow diagrams and its application to generalized recursion theory
An algorithm for the word problem in extensions and the dependence of its complexity on the group representation
An application of results by Hardy, Ramanujan and Karamata to Ackermannian functions.