Search

Answer Set Programming (ASP) is a well-known logic-based formalism that has been used to model and solve a variety of AI problems. For several years, ASP implementations primarily focused on the main computational task: the computation of one answer set of a (logic) program. Nonetheless, several AI problems, that can be conveniently modelled in ASP, require to enumerate solutions characterized by an optimality property that can be expressed in terms of subset-minimality with respect to some objective atoms. In this context, solutions are often either (i) answer sets that are subset-minimal w.r.t. the objective atoms or (ii) atoms that are contained in all subset-minimal answer sets, or (iii) sets of atoms that enforce the absence of answer sets on the ASP program at hand — such sets are referred to as minimal unsatisfiable subsets (MUSes). In all the above-mentioned cases, the corresponding computational task is currently not supported by plain state-of-the-art ASP solvers. In this paper, we study formally these tasks and fill the gap in current implementations by proposing several algorithms to enumerate MUSes and subset-minimal answer sets, as well as perform cautious reasoning on subset-minimal answer sets. We implement our algorithms on top of wasp and perform an experimental analysis on several hard benchmarks showing the good performance of our implementation. [ABSTRACT FROM AUTHOR]

Answer Set Programming (ASP) is a well-established paradigm for declarative programming and nonmonotonic reasoning. ASP allows for flexible modeling using rules. ASP rules induce a set of intended models called answer sets. Incoherence, the non-existence of answer sets, is therefore a feature of ASP, indicating that the rules admit no intended models. However, this feature can also be problematic in certain circumstances: errors that cause incoherence are notoriously difficult to debug, and query answering will not provide any meaningful answers for incoherent programs. Paracoherent semantics have been suggested as a remedy. They extend the classical notion of answer sets to draw meaningful conclusions also from incoherent programs. However, paracoherent semantics have essentially been inapplicable in practice, due to the lack of efficient algorithms and implementations. In this paper, this lack is addressed, and several different algorithms to compute semi-stable and semi-equilibrium models are proposed and implemented within an answer set solving framework. A key role in the framework is played by syntactic program transformations that allow for characterizing paracoherent semantics in terms of the answer sets of transformed programs. Apart from existing transformations from the literature, a novel transformation is also proposed, which provides an alternative characterization of paracoherent semantics in terms of (extended) externally supported models. Notably, the new transformation is more compact than the existing ones, and brings performance benefits. An extensive empirical performance comparison among the algorithms on benchmarks from ASP competitions and a real-world use case is given as well. It shows not only that the methods developed in this paper lead to practically effective systems, but also show a clear advantage of the methods that rely on (extended) externally supported models. [ABSTRACT FROM AUTHOR]

How do cells perceive time? Do cells use temporal information to regulate the production/degradation of their enzymes, membranes, and organelles? Does controlling biological time influence cytoskeletal organization and cellular architecture in ways that confer evolutionary and physiological advantages? Potential answers to these fundamental questions of cell biology have historically revolved around the discussion of 'master' temporal programs, such as the principal cyclin-dependent kinase/cyclin cell division oscillator and the circadian clock. In this review, we provide an overview of the recent evidence supporting an emerging concept of 'autonomous clocks,' which under normal conditions can be entrained by the cell cycle and/or the circadian clock to run at their pace, but can also run independently to serve their functions if/when these major temporal programs are halted/abrupted. We begin the discussion by introducing recent developments in the study of such clocks and their roles at different scales and complexities. We then use current advances to elucidate the logic and molecular architecture of temporal networks that comprise autonomous clocks, providing important clues as to how these clocks may have evolved to run independently and, sometimes at the cost of redundancy, have strongly coupled to run under the full command of the cell cycle and/or the circadian clock. Next, we review a list of important recent findings that have shed new light onto potential hallmarks of autonomous clocks, suggestive of prospective theoretical and experimental approaches to further accelerate their discovery. Finally, we discuss their roles in health and disease, as well as possible therapeutic opportunities that targeting the autonomous clocks may offer., Competing Interests: MM, FE, AA, FD, AB, MA No competing interests declared, (© 2021, Mofatteh et al.)