Deciding whether a relation   defined in
Presburger logic  
can be defined in weaker logics

Christian Choffrut

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

On guessing whether a sequence has a certain property.

Alexander, Samuel (2011)

Journal of Integer Sequences [electronic only]

Similarity:

Intensional logic with deep cases.

Prešić, Marica D. (1993)

Publications de l'Institut Mathématique. Nouvelle Série

Similarity:

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