### A calculus for finitely satisfiable formulas with identity.

Skip to main content (access key 's'),
Skip to navigation (access key 'n'),
Accessibility information (access key '0')

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

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

We consider shifted equality sets of the form ${E}_{G}(a,{g}_{1},{g}_{2})=\{w\mid {g}_{1}\left(w\right)=a{g}_{2}\left(w\right)\}$, 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\left({E}_{G}\left(J\right)\right)$, where $h$ is a coding and ${E}_{G}\left(J\right)$ 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={\pi}_{A}\left({E}_{G}(a,{g}_{1},{g}_{2})\right)$ for some (nonerasing) morphisms ${g}_{1}$ and ${g}_{2}$ and a letter $a$, where ${\pi}_{A}$ deletes the letters not in $A$. Then we deduce...