Loop-separable programs and their first-order definability |
| |
| Authors: | Yin Chen Fangzhen Lin Yan Zhang Yi Zhou |
| |
| Affiliation: | 1. Department of Computer Science, South China Normal University, Guangzhou, Guangdong, China;2. Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong;3. Intelligent Systems Lab, School of Computing and Mathematics, University of Western Sydney, Penrith South DC, NSW 1797, Australia |
| |
| 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. 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
