MPI-INF Logo
Publications

Server    halma.mpi-inf.mpg.de

Proceedings Article, Paper


@InProceedings
Beitrag in Tagungsband, Workshop
Author, Editor
Author(s):
Ganzinger, Harald
Jacquemard, Florent
Veanes, Margus		dblp
dblp
dblp
Editor(s):
Hsiang, Jieh
Ohori, Atsushi		dblp
dblp
BibTeX cite key*:
GanzingerJacquemardVeanes-98
Title, Booktitle
Title*:
Rigid Reachability
Booktitle*:
Proceedings of the 4th Asian Computing Science Conference on Advances in Computing Science (ASIAN-98)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Manila, The Philippines,
Language:
English
Event Date*
(no longer used):
December, 8-10, 1998
Organization:
Event Start Date:
9 June 2024
Event End Date:
9 June 2024
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1538
Number:
Month:
Pages:
4-21
Year*:
1998
VG Wort Pages:
ISBN/ISSN:
3-540-65388-0
Sequence Number:
DOI:
Note, Abstract, ©
Note:
A full version of this paper is available as MPI-I Research Report MPI-I-98-2-013.
(LaTeX) Abstract:
We show that rigid reachability, the non-symmetric form of rigid
E-unification, is undecidable already in the case of a single
constraint. From this we infer the undecidability of a new
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 in EXPTIME.
HyperLinks / References / URLs:
\hgURL{~hg/drafts/RigidR.ps.gz}
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{GanzingerJacquemardVeanes-98,
AUTHOR = {Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
 EDITOR = {Hsiang, Jieh and Ohori, Atsushi},
 TITLE = {Rigid Reachability},
 BOOKTITLE = {Proceedings of the 4th Asian Computing Science Conference on Advances in Computing Science (ASIAN-98)},
 PUBLISHER = {Springer},
 YEAR = {1998},
 VOLUME = {1538},
 PAGES = {4--21},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Manila, The Philippines,},
 ISBN = {3-540-65388-0},
}

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)
Christine Kiesel		Created
03/30/1999 10:05:03 AM
Revisions
8.
7.
6.
5.
4.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel		Edit Dates
07.04.99 16:38:51
01.04.99 10:54:38
01.04.99 09:44:27
30/03/99 11:32:53
30/03/99 11:08:37