MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Vorobyov, Sergeidblp
Editor(s):
Jaffar, Joxan
Yap, Roland H. C.		dblp
dblp
BibTeX cite key*:
Vorobyov96ASIAN96
Title, Booktitle
Title*:
On the bounded theories of finite trees
Booktitle*:
Second Asian Computing Science Conference, ASIAN'96
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Singapore
Language:
English
Event Date*
(no longer used):
December 2-5, 1996
Organization:
Event Start Date:
14 May 2024
Event End Date:
14 May 2024
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Full paper
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1179
Number:
Month:
Pages:
152-161
Year*:
1996
VG Wort Pages:
ISBN/ISSN:
3-540-62031-1
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 The theory of finite trees is the full first-order theory of
equality in the Herbrand universum (the set of ground terms) over a
functional signature containing non-unary function symbols and
constants. Albeit decidable, this theory turns out to be of
non-elementary complexity [Vorobyov96CADE96].

To overcome the intractability of the theory of finite trees, we
introduce in this paper the bounded theory of finite trees.
This theory replaces the usual equality $=$, interpreted as
identity, with the infinite family of approximate equalities
``down to a fixed given depth'' $\{=^d\}_{d\in\omega}$, with $d$
written in binary notation, and $s=^dt$ meaning that the ground
terms $s$ and $t$ coincide if all their branches longer than $d$ are
cut off.

By using a refinement of Ferrante-Rackoff's complexity-tailored
Ehrenfeucht-Fraisse games, we demonstrate that the bounded theory of finite trees
can be decided within linear double exponential space
$2^{2^{cn}}$ ($n$ is the length of input) for some constant $c>0$.
Keywords:
Decision complexity of logical theories
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:
@INPROCEEDINGS{Vorobyov96ASIAN96,
AUTHOR = {Vorobyov, Sergei},
 EDITOR = {Jaffar, Joxan and Yap, Roland H. C.},
 TITLE = {On the bounded theories of finite trees},
 BOOKTITLE = {Second Asian Computing Science Conference, ASIAN'96},
 PUBLISHER = {Springer},
 YEAR = {1996},
 TYPE = {Full paper},
 VOLUME = {1179},
 PAGES = {152--161},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Singapore},
 ISBN = {3-540-62031-1},
}

Entry last modified by Uwe Brahm, 03/12/2010
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)
Sergei Vorobyov		Created
03/11/1997 12:46:28 PM
Revision
1.
0.


Editor
Uwe Brahm
Sergei Vorobyov


Edit Date
24.03.97 21:12:51
11/03/97 12:46:30