hide
Free keywords:
-
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.
