Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Logic with Equality: Partisan Corroboration and Shifted Pairing

Gurevich, Y., & Veanes, M. (1999). Logic with Equality: Partisan Corroboration and Shifted Pairing. Information and Computation, 152(2), 205-235.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Gurevich, Yuri, Autor
Veanes, Margus1, Autor           
Affiliations:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: Herbrand's theorem plays a fundamental role in automated theorem proving methods based on tableaux. The crucial step in procedures based on such methods can be described as the \emph{corroboration} problem or the \emph{Herbrand skeleton} problem, where, given a positive integer $m$, called \emph{multiplicity}, and a quantifier free formula, one seeks a valid disjunction of $m$ instantiations of that formula. In the presence of \emph{equality}, which is the case in this paper, this problem was recently shown to be undecidable. The main contributions of this paper are two theorems. The first, the \emph{Partisan Corroboration Theorem}, relates corroboration problems with different multiplicities. The second, the \emph{Shifted Pairing Theorem}, is a finite tree automata formalization of a technique for proving undecidability results through direct encodings of valid Turing machine computations. These theorems are used in the paper to explain and sharpen several recent undecidability results related to the \emph{corroboration} problem, the \emph{simultaneous rigid E-unification} problem and the \emph{prenex fragment of intuitionistic logic with equality}.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-121999
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 519740
Anderer: Local-ID: C1256104005ECAFC-BF6765C77376770AC125675B0065156D-GurevichVeanes99
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Information and Computation
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 152 (2) Artikelnummer: - Start- / Endseite: 205 - 235 Identifikator: -