First-Order Indefinability of Answer Set Programs on Finite Structures

Yin Chen; Yan Zhang; Yi Zhou

First-Order Indefinability of Answer Set Programs on Finite Structures

Yin Chen
, Yan Zhang
, Yi Zhou

School of Computer, Data & Mathematical Sciences

South China Normal University

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

1 Citation (Scopus)

Abstract

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, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fraïssé game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.

Original language	English
Title of host publication	Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010
Publisher	AAAI Press
Pages	285-290
Number of pages	6
ISBN (Electronic)	9781577354642
Publication status	Published - 15 Jul 2010
Event	24th AAAI Conference on Artificial Intelligence, AAAI 2010 - Atlanta, United States Duration: 11 Jul 2010 → 15 Jul 2010

Publication series

Name	Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010

Conference

Conference	24th AAAI Conference on Artificial Intelligence, AAAI 2010
Country/Territory	United States
City	Atlanta
Period	11/07/10 → 15/07/10

Bibliographical note

Publisher Copyright:
© 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Cite this

@inproceedings{0d0ad12fce384b389b9ce4b398c11d57,

title = "First-Order Indefinability of Answer Set Programs on Finite Structures",

abstract = "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, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fra{\"i}ss{\'e} game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.",

author = "Yin Chen and Yan Zhang and Yi Zhou",

note = "Publisher Copyright: {\textcopyright} 2010, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 24th AAAI Conference on Artificial Intelligence, AAAI 2010 ; Conference date: 11-07-2010 Through 15-07-2010",

year = "2010",

month = jul,

day = "15",

language = "English",

series = "Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010",

publisher = "AAAI Press",

pages = "285--290",

booktitle = "Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010",

}

Chen, Y, Zhang, Y & Zhou, Y 2010, First-Order Indefinability of Answer Set Programs on Finite Structures. in Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010. Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010, AAAI Press, pp. 285-290, 24th AAAI Conference on Artificial Intelligence, AAAI 2010, Atlanta, United States, 11/07/10.

First-Order Indefinability of Answer Set Programs on Finite Structures. / Chen, Yin; Zhang, Yan; Zhou, Yi.
Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010. AAAI Press, 2010. p. 285-290 (Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010).

Research output: Chapter in Book / Conference Paper › Conference Paper › peer-review

TY - GEN

T1 - First-Order Indefinability of Answer Set Programs on Finite Structures

AU - Chen, Yin

AU - Zhang, Yan

AU - Zhou, Yi

PY - 2010/7/15

Y1 - 2010/7/15

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, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fraïssé game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.

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, otherwise this program is first-order indefinable on finite structures. In this paper, we study the problem of first-order indefinability of answer set programs. We provide an Ehrenfeucht-Fraïssé game-theoretic characterization for the first-order indefinability of answer set programs on finite structures. As an application of this approach, we show that the well-known finding Hamiltonian cycles program is not first-order definable on finite structures. We then define two notions named the 0-1 property and unbounded cycles or paths under the answer set semantics, from which we develop two sufficient conditions that may be effectively used in proving a program's first-order indefinability on finite structures under certain circumstances.

UR - https://www.scopus.com/pages/publications/85167416579

M3 - Conference Paper

AN - SCOPUS:85167416579

T3 - Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010

SP - 285

EP - 290

BT - Proceedings of the 24th AAAI Conference on Artificial Intelligence, AAAI 2010

PB - AAAI Press

T2 - 24th AAAI Conference on Artificial Intelligence, AAAI 2010

Y2 - 11 July 2010 through 15 July 2010

ER -

First-Order Indefinability of Answer Set Programs on Finite Structures

Abstract

Publication series

Conference

Bibliographical note

Other files and links

Fingerprint

Cite this