DocumentCode :
304655
Title :
Arc-consistency in dynamic CSPs is no more prohibitive
Author :
Debruyne, Romuald
Author_Institution :
LIRMM, Montpellier, France
fYear :
1996
fDate :
16-19 Nov. 1996
Firstpage :
299
Lastpage :
306
Abstract :
Constraint satisfaction problems (CSPs) are widely used in Artificial Intelligence. The problem of the existence of a solution in a CSP being NP-complete, filtering techniques and particularly arc-consistency are essential. They remove some local inconsistencies and so make the search easier. Since many problems in AI require a dynamic environment, the model was extended to dynamic CSPs (DCSPs) and some incremental arc-consistency algorithms were proposed. However, all of them have important drawbacks. DnAC-4 has an expensive worst-case space complexity and a bad average time complexity. AC/DC has a non-optimal worst-case time complexity which prevents from taking advantage of its good space complexity. The algorithm we present in this paper has both lower space requirements and better time performances than DnAC-4 while keeping an optimal worst case time complexity.
Keywords :
artificial intelligence; computational complexity; constraint handling; DnAC-4; NP-complete; arc-consistency; artificial intelligence; average time complexity; constraint satisfaction problems; dynamic CSPs; dynamic environment; filtering techniques; local inconsistencies; worst-case space complexity; Artificial intelligence; Filtering; Labeling; Layout; NP-complete problem; Natural languages; Peptides; RNA; Sequences; Whales;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Tools with Artificial Intelligence, 1996., Proceedings Eighth IEEE International Conference on
ISSN :
1082-3409
Print_ISBN :
0-8186-7686-7
Type :
conf
DOI :
10.1109/TAI.1996.560467
Filename :
560467
Link To Document :
بازگشت