Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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