A Model-Theoretic View on Qualitative Constraint Reasoning

被引：27
作者：
Bodirsky, Manuel [1 ]
Jonsson, Peter [2 ]
机构：
[1] Tech Univ Dresden, Inst Algebra, D-01062 Dresden, Germany
[2] Linkoping Univ, Dept Comp Sci, SE-58183 Linkoping, Sweden
来源：
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH | 2017年 / 58卷
基金：
欧洲研究理事会;
关键词：
EXPRESSIVE POWER; SATISFACTION; COMPLEXITY; TRACTABILITY; ALGEBRAS;
D O I：
10.1613/jair.5260
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
Qualitative reasoning formalisms are an active research topic in artificial intelligence. In this survey we present a model-theoretic perspective on qualitative constraint reasoning and explain some of the basic concepts and results in an accessible way. In particular, we discuss the significance of omega-categoricity for qualitative reasoning, of primitive positive interpretations for complexity analysis, and of Datalog as a unifying language for describing local consistency algorithms.
引用
收藏
页码：339 / 385
页数：47
相关论文
共 95 条
[1]  
Abiteboul S, 1995, FDN DATABASES
[2]   MAINTAINING KNOWLEDGE ABOUT TEMPORAL INTERVALS [J].
ALLEN, JF .
COMMUNICATIONS OF THE ACM, 1983, 26 (11) :832-843
[3]  
Amaneddine Nouhad, 2013, P IJCAI, P696
[4]  
[Anonymous], 1990, Logic, Programming and Prolog
[5]  
[Anonymous], 1979, Introduction to Automata Theory, Languages, and Computation
[6]  
[Anonymous], 2002, MODEL THEORY INTRO
[7]  
[Anonymous], 1993, ENCY MATH APPL, DOI DOI 10.1017/CBO9780511551574
[8]  
Apt KR, 2006, LECT NOTES COMPUT SC, V4204, P29
[9]   Affine systems of equations and counting infinitary logic [J].
Atserias, Albert ;
Bulatov, Andrei ;
Dawar, Anuj .
THEORETICAL COMPUTER SCIENCE, 2009, 410 (18) :1666-1683
[10]  
Balbiani P., 1999, Progress in Artificial Intelligence. 9th Portuguese Conference on Artificial Intelligence, EPIA'99. Proceedings (Lecture Notes in Artificial Intelligence Vol.1695), P75
12345678910