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:








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

Publisher's
Name:

Academic Press

Publisher's URL:


Publisher's
Address:


ISSN:


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, Abstract, ©

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},
PUBLISHER = {Academic Press},
YEAR = {1999},
NUMBER = {2},
VOLUME = {152},
PAGES = {205--235},
}


Entry last modified by Uwe Brahm, 03/12/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Margus Veanes
Created
04/22/1999 08:24:06 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Anja Becker
Christine Kiesel
Margus Veanes
Margus Veanes
Edit Dates
10.04.2000 13:59:18
04.04.2000 09:59:10
23/03/2000 11:29:30
22/04/99 20:26:48
22/04/99 20:24:06