Physical Sciences and Mathematics Commons^™

Weighted-Sequence Problem: Asp Vs Casp And Declarative Vs Problem-Oriented Solving, Yuliya Lierler, Shaden Smith

Computer Science Faculty Proceedings & Presentations

Search problems with large variable domains pose a challenge to current answer-set programming (ASP) systems as large variable domains make grounding take a long time, and lead to large ground theories that may make solving infeasible. To circumvent the “grounding bottleneck” researchers proposed to integrate constraint solving techniques with ASP in an approach called constraint ASP (CASP). In the paper, we evaluate an ASP system clingo and a CASP system clingcon on a handcrafted problem involving large integer domains that is patterned after the database task of determining the optimal join order. We find that search methods used by clingo …

On The Relation Of Constraint Answer Set Programming Languages And Algorithms, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Recently a logic programming language AC was proposed by Mellarkod et al. (2008) to integrate answer set programming (ASP) and constraint logic programming. Similarly, Gebser et al. (2009) proposed a CLINGCON language integrating ASP and finite domain constraints. These languages allow new efficient inference algorithms that combine traditional ASP procedures and other methods in constraint programming. In this paper we show that a transition system introduced by Nieuwenhuis et al. (2006) to model SAT solvers can be extended to model the “hybrid” ACSOLVER algorithm by Mellarkod et al. developed for simple AC programs and the CLINGCON algorithm by Gebser et …

Practical And Methodological Aspects Of The Use Of Cutting-Edge Asp Tools, Marcello Balduccini, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

In the development of practical applications of answer set programming (ASP), encodings that use well-established solvers such as CLASP and DLV are sometimes affected by scalability issues. In those situations, one can resort to more sophisticated ASP tools exploiting, for instance, incremental and constraint ASP. However, today there is no specific methodology for the selection or use of such tools. In this paper we describe how we used such cutting-edge ASP tools on challenging problems from the Third Answer Set Programming Competition. We view this paper as a first step in the development of a general methodology for the use …

Surviving Solver Sensitivity: An Asp Practitioner’S Guide, Bryan Silverthorn, Yuliya Lierler, Marius Schneider

Computer Science Faculty Proceedings & Presentations

Answer set programming (ASP) is a declarative programming formalism that allows a practitioner to specify a problem without describing an algorithm for solving it. In ASP, the tools for processing problem specifications are called answer set solvers. Because specified problems are often NP complete, these systems often require significant computational effort to succeed. Furthermore, they offer different heuristics, expose numerous parameters, and their running time is sensitive to the configuration used. Portfolio solvers and automatic algorithm configuration systems are recent attempts to automate the problem of manual parameter tuning, and to mitigate the burden of identifying the right solver configuration. …

Termination Of Grounding Is Not Preserved By Strongly Equivalent Transformations, Yuliya Lierler, Vladimir Lifschitz

Computer Science Faculty Proceedings & Presentations

The operation of a typical answer set solver begins with grounding—replacing the given program with a program without variables that has the same answer sets. When the given program contains function symbols, the process of grounding may not terminate. In this note we give an example of a pair of consistent, strongly equivalent programs such that one of them can be grounded by LPARSE, DLV, and gringo, and the other cannot.

Parsing Combinatory Categorial Grammar With Answer Set Programming: Preliminary Report, Yuliya Lierler, Peter Schüller

Computer Science Faculty Proceedings & Presentations

Combinatory categorial grammar (CCG) is a grammar formalism used for natural language parsing. CCG assigns structured lexical categories to words and uses a small set of combinatory rules to combine these categories to parse a sentence. In this work we propose and implement a new approach to CCG parsing that relies on a prominent knowledge representation formalism, answer set programming (ASP) — a declarative programming paradigm. We formulate the task of CCG parsing as a planning problem and use an ASP computational tool to compute solutions that correspond to valid parses. Compared to other approaches, there is no need to …

Weighted-Sequence Problem: Asp Vs Casp And Declarative Vs Problem-Oriented Solving, Yuliya Lierler, Shaden Smith, Miroslaw Truszczyński, Alex Westlund

Computer Science Faculty Proceedings & Presentations

Search problems with large variable domains pose a challenge to current answer-set programming (ASP) systems as large variable domains make grounding take a long time, and lead to large ground theories that may make solving infeasible. To circumvent the “grounding bottleneck” researchers proposed to integrate constraint solving techniques with ASP in an approach called constraint ASP (CASP). In the paper, we evaluate an ASP system CLINGO and a CASP system CLINGCON on a handcrafted problem involving large integer domains that is patterned after the database task of determining the optimal join order. We find that search methods used by CLINGO …

A Transition System For Ac Language Algorithms, Yuliya Lierler, Yaunlin Zhang

Computer Science Faculty Proceedings & Presentations

Recently a logic programming language AC was proposed by Mellarkod et al. (2008) to integrate answer set programming (ASP) and constraint logic programming. In a similar vein, Gebser et al. (2009) proposed a CLINGCON language integrating ASP and finite domain constraints. A distinguishing feature of these languages is their capacity to allow new efficient inference algorithms that combine traditional ASP procedures and other efficient methods in constraint programming. In this paper we show that a transition system introduced by Nieuwenhuis et al. (2006) can be extended to model the “hybrid” ACSOLVER algorithm, by Mellarkod et al., designed for processing a …

Asp-Based Problem Solving With Cutting-Edge Tools, Marcello Balduccini, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

In the development of practical applications of answer set programming (ASP), encodings that use well-established solvers such as CLASP and DLV are sometimes affected by scalability issues. In those situations, one can resort to more sophisticated ASP tools exploiting, for instance, incremental and constraint ASP. However, today there is no specific methodology for the selection or use of such tools. In this paper we describe how we used such cutting-edge ASP tools on challenging problems from the Third Answer Set Programming Competition, and outline the methodology we followed. We view this paper as a first step in the development of …

A Dynamic Energy-Aware Model For Scheduling Computationally Intensive Bioinformatics Applications, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

High Performance Computing (HPC) resources are housed in large datacenters, which consume huge amounts of energy and are quickly demanding attention from businesses as they result in high operating costs. On the other hand HPC environments have been very useful to researchers in many emerging areas in life sciences such as Bioinformatics and Medical Informatics. In this paper, we provide a dynamic model for energy aware scheduling (EAS) in a HPC environment; we use a widely used bioinformatics tool named BLAT (BLAST-like alignment tool) running in a HPC environment as our case study. Our proposed EAS model incorporates 2-Phases: an …

Representing Synonymity In Causal Logic And In Logic Programming, Joohyung Lee, Yuliya Lierler, Vladimir Lifschitz, Fangkai Yang

Computer Science Faculty Proceedings & Presentations

We investigate the relationship between rules representing synonymity in nonmonotonic causal logic and in answer set programming. This question is of interest in connection with current work on modular languages for describing actions.

One More Decidable Class Of Finitely Ground Programs, Yuliya Lierler, Vladimir Lifschitz

Computer Science Faculty Proceedings & Presentations

When a logic program is processed by an answer set solver, the first task is to generate its instantiation. In a recent paper, Calimeri et el. made the idea of efficient instantiation precise for the case of disjunctive programs with function symbols, and introduced the class of “finitely ground” programs that can be efficiently instantiated. Since that class is undecidable, it is important to find its large decidable subsets. In this paper, we introduce such a subset—the class of argumentrestricted programs. It includes, in particular, all finite domain programs, ω-restricted programs, and λ-restricted programs.

Dynamic Energy Aware Task Scheduling For Periodic Tasks Using Expected Execution Time Feedback, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

Scheduling dependent tasks is one of the most challenging problems in parallel and distributed systems. It is known to be computationally intractable in its general form as well as several restricted cases. An interesting application of scheduling is in the area of energy awareness for mobile battery operated devices where minimizing the energy utilized is the most important scheduling policy consideration. A number of heuristics have been developed for this consideration. In this paper, we study the scheduling problem for a particular battery model. In the proposed work, we show how to enhance a well know approach of accounting for …

Abstract Answer Set Solvers, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Nieuwenhuis, Oliveras, and Tinelli showed how to describe enhancements of the Davis-Putnam-Logemann-Loveland algorithm using transition systems, instead of pseudocode. We design a similar framework for three algorithms that generate answer sets for logic programs: SMODELS, ASP-SAT with Backtracking, and a newly designed and implemented algorithm SUP. This approach to describing answer set solvers makes it easier to prove their correctness, to compare them, and to design new systems.

On The Tradeoff Between Speedup And Energy Consumption In High Performance Computing – A Bioinformatics Case Study, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

High Performance Computing has been very useful to researchers in the Bioinformatics, Medical and related fields. The bioinformatics domain is rich in applications that require extracting useful information from very large and continuously growing sequence of databases. Automated techniques such as DNA sequencers, DNA microarrays & others are continually growing the dataset that is stored in large public databases such as GenBank and Protein DataBank. Most methods used for analyzing genetic/protein data have been found to be extremely computationally intensive, providing motivation for the use of powerful computers or systems with high throughput characteristics. In this paper, we provide a …

Dynamic Energy Aware Task Scheduling Using Run-Queue Peek, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

Scheduling dependent tasks is one of the most challenging problems in parallel and distributed systems. It is known to be computationally intractable in its general form as well as several restricted cases. An interesting application of scheduling is in the area of energy awareness for mobile battery operated devices where minimizing the energy utilized is the most important scheduling policy consideration. A number of heuristics have been developed for this consideration. In this paper, we study the scheduling problem for a particular battery model. In the proposed work, we show how to enhance a well know approach of accounting for …

Head-Elementary-Set-Free Logic Programs, Martin Gebser, Joohyung Lee, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

The recently proposed notion of an elementary set yielded a refinement of the theorem on loop formulas, telling us that the stable models of a disjunctive logic program can be characterized by the loop formulas of its elementary sets. Based on the notion of an elementary set, we propose the notion of head-elementary-set-free (HEF) programs, a more general class of disjunctive programs than head-cycle-free (HCF) programs proposed by Ben-Eiiyahu and Dechter. that can still be turned into nondisjunct:ive programs in polynomial time and space by "shifting" the head atoms into the body. We show several properties of HEF programs that …

Elementary Sets For Logic Programs, Martin Gebser, Joohyung Lee, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

By introducing the concepts of a loop and a loop formula, Lin and Zhao showed that the answer sets of a nondisjunctive logic program are exactly the models of its Clark’s completion that satisfy the loop formulas of all loops. Recently, Gebser and Schaub showed that the Lin-Zhao theorem remains correct even if we restrict loop formulas to a special class of loops called “elementary loops.” In this paper, we simplify and generalize the notion of an elementary loop, and clarify its role. We propose the notion of an elementary set, which is almost equivalent to the notion of an …

Model Generation For Generalized Quantifiers Via Answer Set Programming, Yuliya Lierler, Günther Görz

Computer Science Faculty Proceedings & Presentations

For the semantic evaluation of natural language sentences, in particular those containing generalized quantifiers, we subscribe to the generate and test methodology to produce models of such sentences. These models are considered as means by which the sentences can be interpreted within a natural language processing system. The goal of this paper is to demonstrate that answer set programming is a simple, efficient and particularly well suited model generation technique for this purpose, leading to a straightforward implementation.

Experiments With Sat-Based Answer Set Programming, Enrico Giunchiglia, Yuliya Lierler, Marco Maratea, A. Tacchella

Computer Science Faculty Proceedings & Presentations

Answer Set Programming (ASP) emerged in the late 1990s as a new logic programming paradigm which has been successfully applied in various application domains. Propositional satisfiability (SAT) is one of the most studied problems in Computer Science. ASP and SAT are closely related: Recent works have studied their relation, and efficient SAT-based ASP solvers (like assat and Cmodels) exist. In this paper we report about (i) the extension of the basic procedures in Cmodels in order to incorporate the most popular SAT reasoning strategies, and (ii) an extensive comparative analysis involving also other state-of-the-art answer set solvers. The experimental analysis …

Cmodels – Sat-Based Disjunctive Answer Set Solver, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Disjunctive logic programming under the stable model semantics [GL91] is a new methodology called answer set programming (ASP) for solving combinatorial search problems. This programming method uses answer set solvers, such as DLV [Lea05], GNT [Jea05], SMODELS [SS05], ASSAT [LZ02], CMODELS [Lie05a]. Systems DLV and GNT are more general as they work with the class of disjunctive logic programs, while other systems cover only normal programs. DLV is uniquely designed to find the answer sets for disjunctive logic programs. On the other hand, GNT first generates possible stable model candidates and then tests the candidate on the minimality using system …

Cmodels For Tight Disjunctive Logic Programs, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Disjunctive logic programming under the stable model semantics [GL91] is a new answer set programming (ASP) methodology for solving combinatorial search problems. It is a form of declarative programming related to logic programming languages, such as Prolog, where the solutions to a problem are represented by answer sets, and not by answer substitutions produced in response to a query as in convential logic programming. Instead of Prolog systems, this programming method uses answer set solvers, such as smodels1, smodelscc2, cmodels3, dlv4, and gnt1. These systems made it possible for ASP to be successfully applied in such areas as planning, bounded …

Disjunctive Answer Set Programming Via Satisfiability, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Using SAT solvers as inference engines in answer set programming systems showed to be a promising approach in building efficient systems. Nowadays SAT based answer set programming systems successfully work with nondisjunctive programs. This paper proposes a way to use SAT solvers for finding answer sets for disjunctive logic programs. We implement two different ways of SAT solver invocation used in nondisjunctive answer set programming. The algorithms are based on the definition of completion for disjunctive programs and the extension of loop formula to the disjunctive case. We propose the necessary modifications to the algorithms known for nondisjunctive programs in …

A Maximal Chain Approach For Scheduling Tasks In A Multiprocessor Systems, Sachin Pawaskar, Hesham Ali

Computer Science Faculty Proceedings & Presentations

Scheduling dependent tasks is one of the most challenging versions of the scheduling problem in parallel and distributed systems. It is known to be computationally intractable in its general form as well as several restricted cases. As a result, researchers have studied restricted forms of the problem by constraining either the task graph representing the parallel tasks or the computer model. Also, in an attempt to solve the problem in the general case, a number of heuristics have been developed. In this paper, we study the scheduling problem for a fixed number of processors m. In the proposed work, we …

Sat-Based Answer Set Programming, Enrico Giunchiglia, Yuliya Lierler, Marco Maratea

Computer Science Faculty Proceedings & Presentations

The relation between answer set programming (ASP) and propositional satisfiability (SAT) is at the center of many research papers, partly because of the tremendous performance boost of SAT solvers during last years. Various translations from ASP to SAT are known but the resulting SAT formula either includes many new variables or may have an unpractical size. There are also well known results showing a one-to-one correspondence between the answer sets of a logic program and the models of its completion. Unfortunately, these results only work for specific classes of problems. In this paper we present a SAT-based decision procedure for …

When Are Behaviour Networks Well-Behaved?, Bernhard Nebel, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

Agents operating in the real world have to deal with a constantly changing and only partially predictable environment and are nevertheless expected to choose reasonable actions quickly. This problem is addressed by a number of action-selection mechanisms. Behaviour networks as proposed by Maes are one such mechanism, which is quite popular. In general, it seems not possible to predict when behaviour networks are well-behaved. However, they perform quite well in the robotic soccer context. In this paper, we analyse the reason for this success by identifying conditions that make behaviour networks goal converging, i.e., force them to reach the goals …

Automatic Compilation Of Protocol Insecurity Problems Into Logic Programming, Alessandro Armondo, Luca Compagna, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

In this paper we show how protocol insecurity problems expressed in a multi-set rewriting formalism can be automatically translated into logic programming problems. The proposed translation paves the way to the construction of model-checkers for security protocols based on state-of-the-art solvers for logic programs. We have assessed the effectiveness of the approach by running the proposed reduction against a selection of insecurity problems drawn from the Clark & Jacob library of security protocols: by running state-of-the-art solvers against the resulting logic programming problems most of the (known) attacks on the considered protocols are found in a few seconds.

Cmodels-2: Sat-Based Answer Set Solver Enhanced To Non-Tight Programs, Yuliya Lierler, Marco Maratea

Computer Science Faculty Proceedings & Presentations

Answer set programming is a new programming paradigm proposed in [1] and [2], and based on the answer set semantics of Prolog [3]. It is well known that an answer set for a logic program is also a model of the program’s completion [4]. The converse is true when the logic program is “tight” [6, 5]. Lin and Zhao [7] showed that for non-tight programs the models of completion which do not correspond to answer sets can be eliminated by adding to the completion what they called “loop formulas”. Nevertheless, their solver ASSAT¹ has some disadvantages: it can work …

A Sat-Based Polynomial Space Algorithm For Answer Set Programming, Enrico Giunchiglia, Marco Maratea, Yuliya Lierler

Computer Science Faculty Proceedings & Presentations

The relation between answer set programming (ASP) and propositional satisfiability (SAT) is at the center of many research papers, partly because of the tremendous performance boost of SAT solvers during last years. Various translations from ASP to SAT are known but the resulting SAT formula either includes many new variables or may have an unpractical size. There are also well known results showing a one-to-one correspondence between the answer sets of a logic program and the models of its completion. Unfortunately, these results only work for specific classes of problems.

In this paper we present a SAT-Based decision procedure for …

Computing Answer Sets Of A Logic Program Via-Enumeration Of Sat Certificates, Yuliya Lierler, Marco Maratea

Computer Science Faculty Proceedings & Presentations

Answer set programming is a new programming paradigm proposed based on the answer set semantics of Prolog. It is well known that an answer set for a logic program is also a model of the program's completion. The converse is true when the logic program is "tight". Lin and Zhao showed that for non-tight programs the models of completion which do not correspond to answer sets can be eliminated by adding to the completion what they called "loop formulas". Nevertheless, their solver ASSAT 1 has some disadvantages: it can work only with basic rules, and it can compute only one …