{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T17:20:20Z","timestamp":1710264020300},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p> In this paper we present a radical approach to obtaining a backtrack-free representation for a constraint satisfaction problem: remove values that lead to dead-ends. This technique does not require additional space but has the drawback of removing solutions. We investigate a number of variations on the basic algorithm including the use of seed solutions, consistency techniques, and a variety of pruning heuristics. Our experimental results indicate that a significant proportion of the solutions to the original problem can be retained especially when an optimization algorithm that specifically searches for such \u201cgood\u201d backtrack-free representations is employed. Further extensions increase solution retention by searching for high-coverage backtrack-free representations, by removing tuples rather than values, and by combining multiple backtrack-free representations. Our approach elucidates, for the first time, a three-way trade-off between space complexity, potential backtracks, and solution loss and enables algorithms that can actively reason about the trade-off between space, backtracks, and solution loss. <\/jats:p>","DOI":"10.1142\/s0218213008004114","type":"journal-article","created":{"date-parts":[[2008,9,2]],"date-time":"2008-09-02T11:01:05Z","timestamp":1220353265000},"page":"703-730","source":"Crossref","is-referenced-by-count":2,"title":["A SPACE-EFFICIENT BACKTRACK-FREE REPRESENTATION FOR CONSTRAINT SATISFACTION PROBLEMS"],"prefix":"10.1142","volume":"17","author":[{"given":"J. CHRISTOPHER","family":"BECK","sequence":"first","affiliation":[{"name":"Department of Mechanical &amp; Industrial Engineering, University of Toronto, 5 King's College Rd., Toronto, Ontario, M5S 3G8, Canada"}]},{"given":"TOM","family":"CARCHRAE","sequence":"additional","affiliation":[{"name":"Actenum Corporation, Suite 410 \u2013 The Landing, 375 Water Street, Vancouver, British Columbia, Canada"}]},{"given":"EUGENE C.","family":"FREUDER","sequence":"additional","affiliation":[{"name":"Cork Constraint Computation Centre, University College Cork, Cork, Ireland"}]},{"given":"GEORG","family":"RINGWELSKI","sequence":"additional","affiliation":[{"name":"Computer Science Department, Hochschule Zittau\/Goerlitz, University of Applied Sciences, Brueckenstrasse 1, 02826 Goerlitz, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(01)00162-X"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/11402763_4"},{"key":"rf4","volume-title":"Constraint processing","author":"Dechter R.","year":"2003"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90002-6"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1145\/359642.359654"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1145\/322290.322292"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00363-6"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00077-6"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213008004114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T02:28:36Z","timestamp":1565144916000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213008004114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":8,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0218213008004114"],"URL":"https:\/\/doi.org\/10.1142\/s0218213008004114","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}