Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Rigid Reachability, The Non-Symmetric Form of Rigid E-Unification

Harald Ganzinger, Florent Jacquemard, and Margus Veanes

Abstract

We show that rigid reachability, the non-symmetric form of rigid E-unification, is already undecidable in the case of a single constraint. From this we infer the undecidability of a new and rather restricted kind of second-order unification. We also show that certain decidable subclasses of the problem which are P-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 PSPACE-complete. Moreover, we identify two decidable non-monadic fragments that are complete for EXPTIME.

Details

Publication typeArticle
Published inInternational Journal of Foundations of Computer Science
Pages3-27
Volume11
Number1
PublisherWorld Scientific Publishing
> Publications > Rigid Reachability, The Non-Symmetric Form of Rigid E-Unification