@INPROCEEDINGS{GanzingerJacquemardVeanes-98-asian,
       AUTHOR = {Ganzinger, H. and Jacquemard, F. and Veanes, M.},
       TITLE = {Rigid Reachability},
	BOOKTITLE          = {Proc.\ ASIAN'98},
        PUBLISHER       = {Springer-Verlag},
        SERIES          = {Lecture Notes in Computer Science},
        ADDRESS         = {Berlin},
        VOLUME             = {1538},
        PAGES           ={4--21},
        YEAR               = {1998},
       ABSTRACT = {
We show that rigid reachability, the non-symmetric form of rigid
$E$-unification, is undecidable already in the case of a single
constraint. From this we infer the undecidability of a new
rather restricted kind of second-order unification.
We also show that certain decidable subclasses of the problem
which are \PTIME-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 in  \EXPTIME.
},
       URL = {\hgURL{~hg/pca.html#98ASIAN}}
}