Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Gurevich, Yuri Veanes, Margus dblp dblp
 BibTeX cite key*: GurevichVeanes99

 Title
 Title*: Logic with Equality: Partisan Corroboration and Shifted Pairing

 Journal
 Journal Title*: Information and Computation Journal's URL: Download URL for the article: Language: English

 Publisher

 Vol, No, pp, Date
 Volume*: 152 Number: 2 Publishing Date: 1999 Pages*: 205-235 Number of VG Pages: Page Start: Page End: Sequence Number: DOI:

 Note: (LaTeX) Abstract: 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}. URL for the Abstract: Categories, Keywords: Theorem Proving, Rigid E-Unification, Finite Tree Automata HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level:

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Programming Logics Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat

BibTeX Entry:

@ARTICLE{GurevichVeanes99,
AUTHOR = {Gurevich, Yuri and Veanes, Margus},
TITLE = {Logic with Equality: Partisan Corroboration and Shifted Pairing},
JOURNAL = {Information and Computation},