Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Decidable Fragments of Simultaneous Rigid Reachability

VĂ©ronique Cortier, Harald Ganzinger, Florent Jacquemard, and Margus Veanes

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-unication or SREU. The absence of symmetry enforces us to use dierent methods, than the ones that have been successful in the context of SREU (for example word equations). The methods that we use instead, involve nite (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. These upper bounds have been open already for corresponding fragments of SREU, for which only the hardness results have been known. The rst result indicates the dierence 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.

Details

Publication typeInproceedings
Published inICALP 1999
Pages250-260
SeriesLNCS
PublisherSpringer Verlag
> Publications > Decidable Fragments of Simultaneous Rigid Reachability