{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T07:22:15Z","timestamp":1648711335006},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,3]]},"abstract":"<jats:p> 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 [Formula: see text]-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. <\/jats:p>","DOI":"10.1142\/s012905410000003x","type":"journal-article","created":{"date-parts":[[2002,8,24]],"date-time":"2002-08-24T21:40:19Z","timestamp":1030225219000},"page":"3-27","source":"Crossref","is-referenced-by-count":4,"title":["RIGID REACHABILITY, THE NON-SYMMETRIC FORM OF RIGID E-UNIFICATION"],"prefix":"10.1142","volume":"11","author":[{"given":"HARALD","family":"GANZINGER","sequence":"first","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik, Im Stadtwald, 66123 Saarbr\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FLORENT","family":"JACQUEMARD","sequence":"additional","affiliation":[{"name":"LORIA and INRIA, 615 rue du Jardin Botanique, B.P. 101, 54602 Villers-les-Nancy Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARGUS","family":"VEANES","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA 98052, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90101-5"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90015-A"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80041-1"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(06)80003-4"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90040-2"},{"issue":"2","key":"p_29","first-page":"147","volume":"103","author":"Makanin G.S.","year":"1977","journal-title":"Russian)"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00130-8"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01691346"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410000003X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:34:05Z","timestamp":1565192045000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410000003X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3]]},"references-count":10,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,3]]}},"alternative-id":["10.1142\/S012905410000003X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410000003x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,3]]}}}