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 , 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...
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...
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.