@inproceedings{ganzinger1998rigid,
author = {Ganzinger, Harald and Jacquemard, Florent and Veanes, Margus},
title = {Rigid Reachability},
series = {LNCS},
booktitle = {Proceedings of the 4th Asian Computing Science Conference on Advances in Computing Science (ASIAN 98)},
year = {1998},
month = {January},
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 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 in EXPTIME.},
publisher = {Springer Verlag},
url = {http://approjects.co.za/?big=en-us/research/publication/rigid-reachability/},
pages = {4-21},
volume = {1538},
edition = {Proceedings of the 4th Asian Computing Science Conference on Advances in Computing Science (ASIAN 98)},
}