{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:36Z","timestamp":1760202576004},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2002,1,9]],"date-time":"2002-01-09T00:00:00Z","timestamp":1010534400000},"content-version":"unspecified","delay-in-days":39,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2001,12]]},"abstract":"<jats:p>We introduce Horn linear logic as a comprehensive logical system capable of handling the \ntypical AI problem of making a plan of the actions to be performed by a robot so that he \ncould get into a set of final situations, if he started with a certain initial situation. \nContrary to undecidability of propositional Horn linear logic, the planning problem is \nproved to be decidable for a reasonably wide class of natural robot systems.<\/jats:p><jats:p>The planning problem is proved to be <jats:styled-content style=\"e10\">EXPTIME<\/jats:styled-content>-complete for the robot systems that allow \nactions with non-deterministic effects. Fixing a finite signature, that is a finite set of \npredicates and their finite domains, we get a <jats:italic>polynomial time<\/jats:italic> procedure of making plans for \nthe robot system over this signature.<\/jats:p><jats:p>The planning complexity is reduced to <jats:styled-content style=\"e10\">PSPACE<\/jats:styled-content> for the robot systems with only pure \ndeterministic actions.<\/jats:p><jats:p>As <jats:italic>honest<\/jats:italic> numerical parameters in our algorithms we invoke the length of description of a \nplanning task \u2018from <jats:italic>W<\/jats:italic> to \n<jats:italic>Z\u02dc<\/jats:italic>\u2019 and the Kolmogorov descriptive complexity of <jats:styled-content style=\"e10\">Ax<\/jats:styled-content><jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>, a set of \npossible actions.<\/jats:p>","DOI":"10.1017\/s0960129501003413","type":"journal-article","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T08:22:25Z","timestamp":1217492545000},"page":"689-716","source":"Crossref","is-referenced-by-count":15,"title":["The classical AI planning problems in the mirror of Horn linear logic: semantics, expressibility, complexity"],"prefix":"10.1017","volume":"11","author":[{"given":"MAX","family":"KANOVICH","sequence":"first","affiliation":[]},{"given":"JACQUELINE","family":"VAUZEILLES","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2002,1,9]]},"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129501003413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T21:36:03Z","timestamp":1557264963000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129501003413\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,12]]},"references-count":0,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2001,12]]}},"alternative-id":["S0960129501003413"],"URL":"https:\/\/doi.org\/10.1017\/s0960129501003413","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,12]]}}}