{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T18:45:23Z","timestamp":1649011523975},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms\u2014CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than \u03b8<jats:sub>ub<\/jats:sub>, the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than \u03b8<jats:sub>lb<\/jats:sub>, the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions. <\/jats:p>","DOI":"10.1142\/s012905411000774x","type":"journal-article","created":{"date-parts":[[2010,11,24]],"date-time":"2010-11-24T08:39:03Z","timestamp":1290587943000},"page":"1073-1088","source":"Crossref","is-referenced-by-count":8,"title":["PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS"],"prefix":"10.1142","volume":"21","author":[{"given":"JUNPING","family":"ZHOU","sequence":"first","affiliation":[{"name":"School of Computer Science and Technology, Jilin University, QianJin Street, Changchun, 130012, China"},{"name":"Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, QianJin Street, Changchun, 130012, China"}]},{"given":"PING","family":"HUANG","sequence":"additional","affiliation":[{"name":"School of Computer Science, Northeast Normal University, Renmin Street, Changchun, 130117, China"}]},{"given":"MINGHAO","family":"YIN","sequence":"additional","affiliation":[{"name":"School of Computer Science, Northeast Normal University, Renmin Street, Changchun, 130117, China"}]},{"given":"CHUNGUANG","family":"ZHOU","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Jilin University, QianJin Street, Changchun, 130012, China"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(95)00045-3"},{"key":"rf4","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"Remi Monasson","journal-title":"Nature"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-99-00305-7"},{"key":"rf7","first-page":"469","volume":"53","author":"Frieze A.","journal-title":"Journal of Algorithms"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(96)00030-6"},{"key":"rf10","first-page":"93","volume":"12","author":"Xu Ke","journal-title":"Journal of Artificial Intelligence Research"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20015"},{"key":"rf15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1613\/jair.1869","volume":"26","author":"Bryce D.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"rf16","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1613\/jair.1705","volume":"26","author":"Helmert M.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2008.11.012"},{"key":"rf18","doi-asserted-by":"crossref","first-page":"290","DOI":"10.3724\/SP.J.1001.2009.00290","volume":"20","author":"Junping Zhou","journal-title":"Journal of Software"},{"key":"rf21","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"1990"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905411000774X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:24:26Z","timestamp":1565191466000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411000774X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":13,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S012905411000774X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411000774x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}