The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

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