Computational methods for Dynamic Answer Set Programming

Susana Hahn · 2025

Read Computational methods for Dynamic Answer Set Programming by Susana Hahn (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-2502-09228.txt.

Introduction

Susana Hahn sets out a research plan on computer methods for a logic system that can reason over time, in a 2025 paper. The base system solves problems stated as rules and facts, and it is strong at tasks like planning. Daily and factory problems, though, change over time and carry limits on timing. Older logic tools for such problems often lack the flex to model them in full.

Hahn aims to extend the base system with ideas from logics built for change, time, and measured limits. The goal is a tool that can model tangled, shifting problems and still reason fast. Target uses include work plans, routes, and the order of steps on a factory line. The paper frames the plan and its aims rather than reporting a finished system, and it ties the work to real use in industry.

Catalog record

CREATORSusana Hahn
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09228

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Computational methods for Dynamic Answer Set Programming Susana Hahn Abstract 1 Introduction In our daily lives, we commonly encounter problems that require reasoning with time. For instance, planning our day, determining our route to work, or scheduling our tasks. We refer to these problems as ’dynamic’ because they involve movement and change over time, which sometimes includes metric information to express deadlines and durations. For example, getting to the office within the next hour while ensuring that you have had breakfast beforehand. In industrial settings, the complexity of these problems increases significantly. We see this complexity in scenarios such as train scheduling, production sequencing, and many other operations. Therefore, modeling these large-scale problems requires addressing both dynamic aspects and complex combinatorial optimizations, which is a significant challenge. Semantic formalisms for expressing dynamic knowledge have been around for many years. Dynamic logics provide the means to describe ordered events, making them powerful tools for domains that need to capture actions and changes. These formalisms are typically approached from a theoretical perspective, and the systems built around them tend to be single-purpose, lacking the flexibility to fully model complex problems. This creates a need for systems that offer comprehensive modeling capabilities for dynamic domains, efficient solving techniques, and tools for industrial integration. Answer Set Programming (ASP) is a prime candidate for solving knowledge-intensive search and optimization problems. This declarative approach offers a rich modeling language and effective solvers. However, ASP is primarily suited for static knowledge and lacks built-in solutions for managing dynamic knowledge. The overall goal of this research project is to extend ASP into a general-purpose technology for dynamic domains. The first step is to develop the logical foundations for enhancing ASP’s base logic with concepts from dynamic, temporal, and metric logic. Significant progress in this area has already been made by previous efforts of our research group, providing a solid foundation for further development. We need to identify fragments of these languages that offer the necessary modeling power for our target dynamic problems while maintaining properties that allow for formalization and translation using various approaches. These approaches include using different structures, such as automata and other transition systems, and compiling durations into other formalisms, such as linear constraints. Implementing these approaches will leverage existing technology in the ASP system clingo and its surrounding tools. This project will employ advanced programming techniques in ASP to create effective systems for modeling complex dynamic problems. Additionally, we aim to add interactive capabilities to these systems to benefit both modelers and end users. We anticipate that incorporating these features into ASP will enhance users’ ability to model dynamic problems and perform various reasoning tasks. 2 Background Dynamic logics One of the most commonly used temporal logics [ 22 ] is Linear-time Temporal Logic (LTL) [ 36 ] . LTL provides modal operators to express temporal properties such as ◦ (next), \square (always), and \Diamond (eventually). LTL can also be defined in terms of Dynamic Logic (DL) [ 28 ] , which allows for writing regular expressions over (infinite) traces and mixing declarative with procedural specifications. These types of specifications are also targeted by action languages such as GOLOG [ 41 ] , which is based on situation calculus. Another interesting approach is Metric Temporal Logic (MTL) [ 39 ] , which allows measuring time differences between events. This measurement is done by assigning a time value to states. Metric Logic can be used in different applications such as scheduling [ 42 ] , routing [ 38 ] , and more [ 32 ] . Originally, these temporal formalisms were investigated for infinite traces. However, in the past decade, the case of finite traces \cdot_{f} has gained interest, as it aligns with a large range of AI applications and constitutes a computationally more feasible variant. The introduction of \textrm{LTL}_{\!f} and Linear Dynamic Logic over finite traces ( \textrm{LDL}_{\!f} ) [ 20 ] served as a stepping stone to define the syntax and classical semantics under this restriction. There are several tasks addressed by these formalisms and other action theories. The most commonly known are satisfiability checking, model checking, and synthesis [ 48 , 49 , 21 , 50 ] . Furthermore, other more elaborate tasks closer to real-world scenarios include reactive control [ 9 ] , diagnostics [ 34 ] , planning [ 5 , 26 , 6 ] , and verification. Many of these tasks are solved by translating complex constructs into simpler ones, for instance, by reducing MTL into LTL [ 32 ] . Another very common strategy for addressing these problems is mapping them into automata. This automata-theoretic approach involves constructing an automaton that accepts exactly the models of a dynamic formula. This relationship has been extensively researched in areas such as satisfiability checking, model checking, planning [ 5 , 26 , 6 ] , and synthesis [ 48 , 49 , 21 , 50 ] . Non-deterministic finite automata (NFA) [ 31 ] and Deterministic Finite Automata (DFA) have been used for finite traces, though they are of exponential size relative to the input formula. To tackle this issue, [ 20 ] proposed a translation from \textrm{LTL}_{\!f} and \textrm{LDL}_{\!f} to a more elaborate but succinct automaton: Alternating Automaton on Finite Words (AFA) [ 19 , 49 , 20 ] . These automata, an adaptation of Alternating Büchi Automata to finite traces, extend NFAs with universal transitions. This translation, however, led to circular definitions for some dynamic formulas and did not include past operators. These issues were addressed in [ 46 ] , where the authors introduced Automata Linear Dynamic Logic over finite traces (ALDL f ) and presented a translation into even more sophisticated automata: Two-Way Alternating Finite Automata (2AFA) [ 40 , 37 ] . In addition to alternation, this type of automaton allows multiple head movements: stationary, left, and right. More evolved translations from metric logic into automata have also been developed, such as translating MTL into Timed Automata [ 43 ] . Answer Set Programming Answer Set Programming (ASP) [ 11 ] is a well-established approach to declarative problem-solving where problems are encoded as logic programs. The combination of its rich modeling language and highly effective solving engines makes ASP a very attractive choice. ASP semantics can be formalized using equilibrium models [ 45 ] of the logic of here-and-there (HT) [ 30 ] . This logic has also been extended to here-and-there with constraints ( \textrm{HT}_{\!c} ) [ 18 ] , which introduces difference constraints, a simplified form of linear constraints, into HT. The ASP system clingo [ 25 ] is known for its high-performing engines. The system provides various tools for extending the language and customizing the solving process. clingo ’s theory language capabilities allow for defining custom syntactic expressions. Additionally, clingo offers two methods for capturing new functionalities [ 35 ] : meta-programming, which uses a reification feature enabling the expression of new functionalities using ASP, and a sophisticated Python API for manipulating and customizing the system’s internal workflow. This customization includes techniques such as multi-shot solving, which allows precise control of the solving process by modularizing the problem. These features have led to the creation of several hybrid ASP systems. In particular, clingcon

Read the complete text