A calculus for finitely satisfiable formulas with identity.
A characterization of r-maximal sets.
A generalization of elementary formal systems
A notion of semigenericity
A survey on real structural complexity theory.
Arithmetical m-degrees.
Boolean algebras, splitting theorems, and sets
Coherent randomness tests and computing the -trivial sets
We introduce Oberwolfach randomness, a notion within Demuth’s framework of statistical tests with moving components; here the components’ movement has to be coherent across levels. We show that a ML-random set computes all -trivial sets if and only if it is not Oberwolfach random, and indeed that there is a -trivial set which is not computable from any Oberwolfach random set. We show that Oberwolfach random sets satisfy effective versions of almost-everywhere theorems of analysis, such as the...
Complete index sets of recursively enumerable families
Cupping and noncapping in the R.E. weak truth table and turing degrees.
Data types as lattices : retractions, closures and projections
Diophantine representation of Mersenne and Fermat primes
Effectiveness - non effectiveness in semialgebraic and PL geometry.
Embedding relations in the lattice of recursively enumerable sets.
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form EG(a,g1,g2) = {ω | g1(ω) = ag2(ω)}, where g1 and g2 are nonerasing morphisms and a is a letter. We are interested in the family consisting of the languages h(EG(J)), where h is a coding and (EG(J)) is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language L ⊆ A* is a projection of a shifted equality set, that is, L = πA(EG(a,g1,g2)) for some (nonerasing) morphisms g1...
Equality sets for recursively enumerable languages
We consider shifted equality sets of the form , where and are nonerasing morphisms and is a letter. We are interested in the family consisting of the languages , where is a coding and is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language is a projection of a shifted equality set, that is, for some (nonerasing) morphisms and and a letter , where deletes the letters not in . Then we deduce...
Good choice sets
Index sets in 0'.
Limiting recursion and the arithmetic hierarchy
Localization o a theorem of Ambos-Spies and the strong anti-splitting property.