@article{ganzinger2000rigid,
author = {Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
title = {Rigid Reachability, The Non-Symmetric Form of Rigid E-Unification},
year = {2000},
month = {January},
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.},
publisher = {World Scientific Publishing},
url = {http://approjects.co.za/?big=en-us/research/publication/rigid-reachability-the-non-symmetric-form-of-rigid-e-unification/},
pages = {3-27},
journal = {International Journal of Foundations of Computer Science},
}