Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Cortier, V.
Ganzinger, Harald
Jacquemard, Florent
Veanes, Margus

dblp
dblp
dblp
dblp



Editor(s):

Wiedermann, Jiri
van Emde Boas, Peter
Nielsen, Mogen

dblp
dblp
dblp



BibTeX cite key*:

Cortier-et-al-99

Title, Booktitle

Title*:

Decidable fragments of simultaneous rigid reachability

Booktitle*:

Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99)

Event, URLs

URL of the conference:


URL for downloading the paper:


Event Address*:

Prague, Czech Republik

Language:

English

Event Date*
(no longer used):

July 11-15, 1999

Organization:


Event Start Date:

19 November 2019

Event End Date:

19 November 2019

Publisher

Name*:

Springer

URL:


Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

1644

Number:


Month:


Pages:

250-260

Year*:

1999

VG Wort Pages:


ISBN/ISSN:

3-540-66224-3

Sequence Number:


DOI:




Note, Abstract, ©

Note:

Full version of this paper is available as
MPI Research Report MPI-I-1999-2-004.

(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.

HyperLinks / References / URLs:

http://www.mpi-sb.mpg.de/~hg/pca.html#99ICALP



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{Cortier-et-al-99,
AUTHOR = {Cortier, V. and Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
EDITOR = {Wiedermann, Jiri and van Emde Boas, Peter and Nielsen, Mogen},
TITLE = {Decidable fragments of simultaneous rigid reachability},
BOOKTITLE = {Proceedings of the 26th International Colloquium on Automata, Languages and Programming (ICALP-99)},
PUBLISHER = {Springer},
YEAR = {1999},
VOLUME = {1644},
PAGES = {250--260},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Prague, Czech Republik},
ISBN = {3-540-66224-3},
}


Entry last modified by Uwe Brahm, 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 05:48:28 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
10.04.2000 13:36:37
28.03.2000 10:42:32
27/01/2000 18:03:57
27/01/2000 10:29:25
27/01/2000 10:26:52