EuDML | Browse

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 $K$ -trivial sets if and only if it is not Oberwolfach random, and indeed that there is a $K$ -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

T. G. McLaughlin (1972)

Compositio Mathematica

Cupping and noncapping in the R.E. weak truth table and turing degrees.

Klaus Ambos-Spies (1985)

Archiv für mathematische Logik und Grundlagenforschung

Data types as lattices : retractions, closures and projections

Luis E. Sanchis (1977)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Diophantine representation of Mersenne and Fermat primes

James Jones (1979)

Acta Arithmetica

Effectiveness - non effectiveness in semialgebraic and PL geometry.

F. Acquistapace, R. Benedetti (1990)

Inventiones mathematicae

Embedding relations in the lattice of recursively enumerable sets.

Donald A. Alton (1975)

Archiv für mathematische Logik und Grundlagenforschung

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider shifted equality sets of the form $E_{G} (a, g_{1}, g_{2}) = {w ∣ g_{1} (w) = a g_{2} (w)}$ , where $g_{1}$ and $g_{2}$ are nonerasing morphisms and $a$ is a letter. We are interested in the family consisting of the languages $h (E_{G} (J))$ , where $h$ is a coding and $E_{G} (J)$ is a shifted equality set. We prove several closure properties for this family. Moreover, we show that every recursively enumerable language $L \subseteq A^{*}$ is a projection of a shifted equality set, that is, $L = π_{A} (E_{G} (a, g_{1}, g_{2}))$ for some (nonerasing) morphisms $g_{1}$ and $g_{2}$ and a letter $a$ , where $π_{A}$ deletes the letters not in $A$ . Then we deduce...

Equality sets for recursively enumerable languages

Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux (2010)

RAIRO - Theoretical Informatics and Applications

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

Currently displaying 1 – 20 of 149

Page 1 Next

Displaying 1 – 20 of 149

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 $Δ_{2}^{0}$ sets

Coherent randomness tests and computing the $K$ -trivial sets

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

Equality sets for recursively enumerable languages

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.

Currently displaying 1 – 20 of 149