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):
Ganzinger, Harald
Jacquemard, Florent
Veanes, Margus		dblp
dblp
dblp

BibTeX cite key*:

GanzingerJacquemardVeanes-00-ijfcs

Title

Title*:

Rigid Reachability: The Non-Symmetric Form of Rigid E-unification

Journal

Journal Title*:

International Journal of Foundations of Computer Science
Journal's URL:

http://www.cs.ucsb.edu/~ijfcs/

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

World Scientific
Publisher's URL:

http://www.wspc.com.sg/

Publisher's
Address:

Singapore
ISSN:

0129-0541

Vol, No, pp, Date

Volume*:

11
Number:

1

Publishing Date:

2000

Pages*:

3-27
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) Abstract:

      We show that rigid reachability, the non-symmetric form of rigid
      E-unification, is already undecidable in the case of a single
      constraint. From this we infer the undecidability of a new
      and rather restricted kind of second-order unification.
      We also show that certain decidable subclasses of the problem
      which are PTIME-complete in the equational case
      become EXPTIME-complete when symmetry is absent.
      By applying automata-theoretic methods,
      simultaneous monadic rigid reachability with ground rules
      is shown to be PSPACE-complete.
      Moreover, we identify two decidable non-monadic fragments that are complete
      for EXPTIME.

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:

      \hgURL{~hg/pja.html#GanzingerJacquemardVeanes-00-ijfcs}

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{GanzingerJacquemardVeanes-00-ijfcs,
AUTHOR = {Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
 TITLE = {Rigid Reachability: The Non-Symmetric Form of Rigid {E}-unification},
 JOURNAL = {International Journal of Foundations of Computer Science},
 PUBLISHER = {World Scientific},
 YEAR = {2000},
 NUMBER = {1},
 VOLUME = {11},
 PAGES = {3--27},
 ADDRESS = {Singapore},
 ISBN = {0129-0541},
}

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
01/26/2001 02:51:13 PM
Revisions
9.
8.
7.
6.
5.		Editor(s)
Christine Kiesel
Anja Becker
Uwe Brahm
Christine Kiesel
Christine Kiesel		Edit Dates
14.09.2001 03:28:03 PM
05.04.2001 15:21:28
04/04/2001 06:36:04 PM
14.03.2001 13:25:25
14.03.2001 13:13:06