Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Decidable fragments of simultaneous rigid reachability

Cortier, Veronique and Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus

MPI-I-1999-2-004. March 1999, 19 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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 forces us to use different
methods, from the ones that have been successful in the context
of SREU in the past (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 rules is PSPACE-complete, and 2) balanced SRR with
ground rules is EXPTIME-complete. 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.

References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-1999-2-004.ps331 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Cortier, Veronique and Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
  TITLE = {Decidable fragments of simultaneous rigid reachability},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-1999-2-004},
  MONTH = {March},
  YEAR = {1999},
  ISSN = {0946-011X},