SM-based Semantics for Answer Set Programs Containing Conditional Literals and Arithmetic
Zachary Hansen, Yuliya Lierler · 2025
Read SM-based Semantics for Answer Set Programs Containing Conditional Literals and Arithmetic by Zachary Hansen, Yuliya Lierler (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-01753.txt.
Introduction
Zachary Hansen and Yuliya Lierler give a formal semantics for a modern feature of answer set programming, the logic programming paradigm behind the CLINGO solver. The feature is conditional literals, subformulas that act like nested implications inside rule bodies and let programs read almost like first-order logic.
Established semantics for programs using conditional literals, and arithmetic along with them, works only through a translation into infinitary propositional logic, which forces grounding. Hansen and Lierler instead build a semantics directly on the SM operator, requiring no grounding at all. Their main theorem proves the new semantics and the established one match in full. So programmers can trust that the cleaner definition captures the same programs' meanings.
Catalog record
| CREATOR | Zachary Hansen, Yuliya Lierler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-01753
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SM-based Semantics for Answer Set Programs Containing Conditional Literals and Arithmetic Zachary Hansen, Yuliya Lierler Abstract Modern answer set programming solvers such as clingo support advanced language constructs that improve the expressivity and conciseness of logic programs. Conditional literals are one such construct. They form “subformulas” that behave as nested implications within the bodies of logic rules. Their inclusion brings the form of rules closer to the less restrictive syntax of first-order logic. These qualities make conditional literals useful tools for knowledge representation. In this paper, we propose a semantics for logic programs with conditional literals and arithmetic based on the SM operator. These semantics do not require grounding, unlike the established semantics for such programs that relies on a translation to infinitary propositional logic. The main result of this paper establishes the precise correspondence between the proposed and existing semantics. 1 Introduction Answer Set Programming (ASP) [ 24 , 25 ] is a declarative programming paradigm that has been applied within a variety of challenging and high-consequence systems such as explainable donor-patient matching [ 6 ] , space shuttle decision support systems [ 2 , 3 ] , train scheduling [ 1 ] , robotics [ 16 ] , and automated fault diagnosis [ 29 ] . ASP programs are concise, human-readable, and benefit from well-defined semantics rooted in mathematical logic – these qualities make ASP programs attractive candidates for formal verification [ 5 ] . Providing high levels of assurance regarding program behavior is particularly crucial for safety-critical applications. This paper is part of a research stream with the long-term goal of supporting rigorous verification of ASP systems. Conditional literals are powerful language features for knowledge representation. Originating in the lparse grounder [ 27 ] , these languages features are now also supported by the answer set solver clingo [ 14 , 15 ] . Intuitively, they represent a nested implication within the body of an ASP rule [ 17 ] . Rules with conditional literals concisely express knowledge that may be difficult to otherwise encode. For instance, conditional literals are widely employed in meta-programming – Listings 4-7 in “How to build your own ASP-based system?!" by Kaminski et al. [ 20 ] define meta encodings which compute the classical and supported models of reified logic programs; these encodings rely heavily on conditional literals. Conditional literals may also make programs easier to formally verify by reducing the number of auxiliary or inessential predicates in a program. Consider Listing 1 , which contains a typical encoding of the graph coloring problem. Listing 1: Graph coloring problem encoding. ⬇ 1 { asg ( V , C )} :- vtx ( V ), col ( C ). 2 :- asg ( V , C1 ), asg ( V , C2 ), C1 != C2 . 3 colored ( V ) :- asg ( V , C ). 4 :- vtx ( V ), not colored ( V ). 5 :- asg ( V1 , C ), asg ( V2 , C ), edge ( V1 , V2 ). The program in this listing can be simplified by replacing lines 3-4 with the following constraint (a rule with an empty head) containing a conditional literal: \displaystyle\;\hbox{:-}\;\penalty\ not\penalty\ asg(V,\penalty\ C)\penalty\ :\penalty\ col(C);\penalty\ vtx(V). (1) This simplification is attractive since it eliminates the auxiliary predicate colored/1 (introduced in line 3 for the sole purpose of stating the subsequent constraint in line 4). We will use rule ( 1 ) as a running example in the remainder of the paper. Typically, the semantics of programs with variables are defined indirectly, via a procedure called grounding . Grounding turns a given program with variables into a propositional one. Then, semantics are defined for the resulting propositional program. This hampers our ability to reason about the behavior of programs independently of a specific grounding context. In 2011, Ferraris, Lee, and Lifschitz proposed semantics for answer set programs that bypasses grounding [ 13 ] . They introduced the SM operator, which turns a program (or, rather, the first-order logic formula associated with the considered program) into a classical second-order formula. The Herbrand models of this formula coincide with the answer sets of the original program. Since then, that approach has been generalized to cover such features of ASP input languages as aggregates [ 7 , 10 ] , arithmetic [ 8 , 21 ] , and conditional literals [ 17 ] . Yet, all of these features were addressed independently of the others. This paper helps to close that gap. Here, we introduce grounding-free SM operator-based semantics for logic programs containing both conditional literals and arithmetic, combining ideas from earlier work on these features [ 8 , 17 , 21 ] . We also show that the proposed characterization coincides with the existing semantics for such programs based on grounding to infinitary propositional logic [ 15 ] ; these are the semantics adhered to by clingo . One of the advantages of the SM -based characterization is that it enables us to construct proofs of correctness in a modular way that does not rely on grounding the program with respect to a specific instance of input data. For instance, this style of verification – which exploits the SM operator’s ability to divide programs into modules – has been employed to demonstrate the adherence of Graph Coloring, Hamiltonian Cycle, and Traveling Salesman problems to natural language specifications [ 5 , 9 ] . This paper extends the class of programs for which such arguments can be constructed. Section 2 defines the language of logic programs considered, and Section 3 provides the essence of the SM characterization for logic programs with conditional literals and arithmetic. Section 4 reviews the established semantics for programs with conditional literals and arithmetic, which relies on a translation from logic programs to infinitary propositional formulas. The main results of this paper –Theorems 5.1 and 5.2 – are given in Section 5 , connecting our SM -based semantics to the established semantics. 2 Syntax of Logic Programs We now present the language of logic programs considered in this paper. It can be viewed as a fragment of the Abstract Gringo (AG) language [ 15 ] ; equivalently, it can be viewed as an extension of the mini- GRINGO language [ 21 ] to rules whose bodies may contain conditional literals. We assume a (program) signature with three countably infinite sets of symbols: numerals , symbolic constants and variables . We also assume a 1-to-1 correspondence between numerals and integers; the numeral corresponding to an integer n is denoted by \overline{n} . A syntactic expression is ground if it contains no variables. A ground expression is precomputed if it contains no operation names. Terms are defined recursively: • Numerals, symbolic constants, variables, or either of the special symbols \mathit{inf} and \mathit{sup} are terms; • if t_{1} , t_{2} are program terms and \circ is one of the operation names \displaystyle+\quad-\quad\times\quad/\quad\setminus\quad.. (2) then t_{1}\circ t_{2} is a term (we write -t to abbreviate the term \overline{0}-t ); • if t_{1} is a program term, then \lvert t_{1}\rvert is a term. We assume that a total order on ground terms is chosen such that • \mathit{inf} is its least