Displaying similar documents to “Deciding whether a relation defined in Presburger logic can be defined in weaker logics”

Arithmetization of the field of reals with exponentiation extended abstract

Sedki Boughattas, Jean-Pierre Ressayre (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:


 Shepherdson proved that a discrete unitary commutative semi-ring satisfies (induction scheme restricted to quantifier free formulas) iff is integral part of a real closed field; and Berarducci asked about extensions of this criterion when exponentiation is added to the language of rings. Let range over axiom systems for ordered fields with exponentiation; for three values of we provide a theory ⌞ T ⌟ in the language of rings plus...

Translation from classical two-way automata to pebble two-way automata

Viliam Geffert, L'ubomíra Ištoňová (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some ℓ additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with ℓ nested pebbles....

The limit lemma in fragments of arithmetic

Vítězslav Švejdar (2003)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

The recursion theoretic limit lemma, saying that each function with a 𝛴 n + 2 graph is a limit of certain function with a 𝛥 n + 1 graph, is provable in B Σ n + 1 .

The Helping Hierarchy

Patrizio Cintioli, Riccardo Silvestri (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Schöning [14] introduced a notion of helping and suggested the study of the class P help ( 𝒞 ) of the languages that can be helped by oracles in a given class 𝒞 . Later, Ko [12], in order to study the connections between helping and "witness searching" , introduced the notion of self-helping for languages. We extend this notion to classes of languages and show that there exists a self-helping class that we call SH which contains all the self-helping classes. We introduce the Helping hierarchy whose levels...