Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2024) | last year (2023) | two years ago (2022) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Bachmair, Leo
Ganzinger, Harald		dblp
dblp

BibTeX cite key*:

BachmairGanzinger-98-jacm

Title

Title*:

Ordered Chaining Calculi for First-Order Theories of Transitive Relations

Journal

Journal Title*:

Journal of the ACM
Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:


Publisher's URL:


Publisher's
Address:


ISSN:

0004-5411

Vol, No, pp, Date

Volume*:

45
Number:

6

Publishing Date:

November 1998

Pages*:

1007-1049
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:

Revised Version of MPI-I-95-2-009.

(LaTeX) Abstract:

In this paper we prove decidability results of
restricted fragments of simultaneous rigid reachability or SRR,
that is the nonsymmetrical form of simultaneous rigid E-unification or SREU.
The absence of symmetry enforces us to use different methods, than the ones
that have been successful in the context of SREU (for example word equations).
The methods that we use instead, involve finite (tree) automata techniques, and
the decidability proofs provide precise computational complexity bounds.
The main results are 1) monadic SRR with ground rule is
PSPACE-complete, and 2) balanced SRR with ground rules is
EXPTIME-complete. These upper bounds have been open already for
corresponding fragments of SREU, for which only the
hardness results have been known.
The first result
indicates the difference in computational power between
fragments of SREU with ground rules and nonground rules,
respectively,
due to a straightforward encoding of word equations in monadic SREU
(with nonground rules).
The second result establishes the decidability and precise complexity of the
largest known subfragment of nonmonadic SREU.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

\hgURL{~hg/pja.html#JACM}

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{BachmairGanzinger-98-jacm,
AUTHOR = {Bachmair, Leo and Ganzinger, Harald},
 TITLE = {Ordered Chaining Calculi for First-Order Theories of Transitive Relations},
 JOURNAL = {Journal of the ACM},
 YEAR = {1998},
 NUMBER = {6},
 VOLUME = {45},
 PAGES = {1007--1049},
 MONTH = {November},
 ISBN = {0004-5411},
 NOTE = {Revised Version of MPI-I-95-2-009.},
}

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
03/29/1999 04:46:05 PM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Harald Ganzinger
Harald Ganzinger		Edit Dates
27/01/2000 18:30:44
27/01/2000 18:24:49
27/01/2000 18:12:59
20/04/99 10:55:13
20/04/99 10:54:37