Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Ganzinger, Harald
Nieuwenhuis, Robert
Nivela, Pilar

dblp
dblp
dblp

Not MPG Author(s):

Nieuwenhuis, Robert
Nivela, Pilar

Editor(s):

Goré, Rajeev
Leitsch, Alexander
Nipkow, Tobias

dblp
dblp
dblp

Not MPII Editor(s):

Goré, Rajeev
Leitsch, Alexander
Nipkow, Tobias

BibTeX cite key*:

GanzingerNieuwenhuisNivela-01-ijcar

Title, Booktitle

Title*:

Context trees


_01IJCAR-1.pdf (148.9 KB)

Booktitle*:

Automated reasoning : First International Joint Conference, IJCAR 2001

Event, URLs

URL of the conference:

http://www.dii.unisi.it/~ijcar/

URL for downloading the paper:


Event Address*:

Siena, Italy

Language:

English

Event Date*
(no longer used):

-- June 18-22, 2001

Organization:


Event Start Date:

18 June 2001

Event End Date:

22 June 2001

Publisher

Name*:

Springer

URL:

http://www.springer.de/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Artificial Intelligence

Volume:

2083

Number:


Month:


Pages:

242-256

Year*:

2001

VG Wort Pages:


ISBN/ISSN:

3-540-42254-4

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Indexing data structures are well-known to be crucial for the
efficiency of the current state-of-the-art theorem provers.
Examples are \emph{discrimination trees}, which are like tries
where terms are seen as strings and common prefixes are shared,
and \emph{substitution trees}, where terms keep their tree
structure and all common \emph{contexts} can be shared.
Here we describe a new indexing data structure, \emph{context
trees}, where, by means of a limited kind of context variables,
also common subterms can be shared, even if they occur below
different function symbols.
Apart from introducing the concept, we also provide evidence
for its practical value. We describe an implementation of context
trees based on Curry terms and on an extension of substitution
trees with equality constraints and where one does not
distinguish between \emph{internal} and \emph{external}
variables. Experiments with matching show that our preliminary
implementation is already competitive with tightly coded current
state-of-the-art implementations of the other main techniques.
In particular space consumption of context trees
is substantially less than for other index structures.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Programming Logics Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{GanzingerNieuwenhuisNivela-01-ijcar,
AUTHOR = {Ganzinger, Harald and Nieuwenhuis, Robert and Nivela, Pilar},
EDITOR = {Gor{\'e}, Rajeev and Leitsch, Alexander and Nipkow, Tobias},
TITLE = {Context trees},
BOOKTITLE = {Automated reasoning : First International Joint Conference, IJCAR 2001},
PUBLISHER = {Springer},
YEAR = {2001},
VOLUME = {2083},
PAGES = {242--256},
SERIES = {Lecture Notes in Artificial Intelligence},
ADDRESS = {Siena, Italy},
ISBN = {3-540-42254-4},
}


Entry last modified by Christine Kiesel, 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)
Christine Kiesel
Created
08/27/2001 05:06:26 PM
Revisions
27.
26.
25.
24.
23.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
01.09.2003 16:59:35
01.09.2003 16:57:53
01.09.2003 14:36:44
29.07.2003 14:41:16
29.07.2003 14:40:20
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
_01IJCAR-1.pdf