TY - JOUR
T1 - Loop-separable programs and their first-order definability
AU - Chen\, Yin
AU - Yin, Fangzhen
AU - Lin, Fangzhen
AU - Zhang, Yan
PY - 2011
Y1 - 2011
N2 - An answer set program with variables is first-order definable on finite structures if the set of its finite answer sets can be captured by a first-order sentence. Characterizing classes of programs that are first-order definable on finite structures is theoretically challenging and of practical relevance to answer set programming. In this paper, we identify a non-trivial class of answer set programs called loop-separable programs and show that they are first-order definable on finite structures.
AB - An answer set program with variables is first-order definable on finite structures if the set of its finite answer sets can be captured by a first-order sentence. Characterizing classes of programs that are first-order definable on finite structures is theoretically challenging and of practical relevance to answer set programming. In this paper, we identify a non-trivial class of answer set programs called loop-separable programs and show that they are first-order definable on finite structures.
UR - http://handle.uws.edu.au:8081/1959.7/557387
U2 - 10.1016/j.artint.2010.12.001
DO - 10.1016/j.artint.2010.12.001
M3 - Article
SN - 0004-3702
VL - 175
SP - 890
EP - 913
JO - Artificial Intelligence
JF - Artificial Intelligence
IS - 45385
ER -