Context trees

Ganzinger, Harald; Nieuwenhuis, Robert; Nivela, Pilar

Context trees

Ganzinger, H., Nieuwenhuis, R., & Nivela, P. (2001). Context trees. In R., Goré, A., Leitsch, & T., Nipkow (Eds.), Automated reasoning: First International Joint Conference, IJCAR 2001 (pp. 242-256). Berlin, Germany: Springer.

Item is 公開

表示: 全項目非表示: 全項目

基本情報

表示: 非表示:

アイテムのパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-3209-0 版のパーマリンク: https://hdl.handle.net/11858/00-001M-0000-000F-320C-A

資料種別: 会議論文

ファイル

表示: ファイル

非表示: ファイル

:

_01IJCAR-1.pdf (全文テキスト（全般）), 149KB

ファイルのパーマリンク:
-

ファイル名:
_01IJCAR-1.pdf

説明:
-

OA-Status:

閲覧制限:
非公開

MIMEタイプ / チェックサム:
application/pdf

技術的なメタデータ:

著作権日付:
-

著作権情報:
-

CCライセンス:
-

作成者

表示:

非表示:

作成者:
Ganzinger, Harald¹, 著者
Nieuwenhuis, Robert¹, 著者
Nivela, Pilar¹, 著者

所属:
1Programming Logics, MPI for Informatics, Max Planck Society, ou_40045

内容説明

表示:

非表示:

キーワード: -

要旨: 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.

資料詳細

表示:

非表示:

言語: eng - English

日付: 修正: 2010-03-12出版: 2001

出版の状態: 出版

ページ: -

出版情報: -

目次: -

査読: -

識別子（DOI, ISBNなど）: eDoc: 519831
その他: Local-ID: C1256104005ECAFC-EB2E979F49F72498C1256AB50052FCC3-GanzingerNieuwenhuisNivela-01-ijcar

学位: -

訴訟

表示:

Project information

表示:

出版物 1

表示:

非表示:

出版物名: Automated reasoning : First International Joint Conference, IJCAR 2001

種別: 会議論文集

著者・編者:
Goré, Rajeev, 編集者
Leitsch, Alexander, 編集者
Nipkow, Tobias, 編集者

所属:
-

出版社, 出版地: Berlin, Germany : Springer

ページ: - 巻号: - 通巻号: - 開始・終了ページ: 242 - 256 識別子（ISBN, ISSN, DOIなど）: ISBN: 3-540-42254-4

出版物 2

表示:

非表示:

出版物名: Lecture Notes in Artificial Intelligence

種別: 連載記事

著者・編者:

所属:

出版社, 出版地: -

ページ: - 巻号: 2083 通巻号: - 開始・終了ページ: - 識別子（ISBN, ISSN, DOIなど）: -

アイテム詳細

基本情報

ファイル

関連URL

作成者

内容説明

資料詳細

関連イベント

訴訟

Project information

出版物 1

出版物 2