Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 8 of 8
Full-Text Articles in Physical Sciences and Mathematics
Abstract Argumentation And Answer Set Programming: Two Faces Of Nelson’S Logic, Jorge Fandinno, Luis Fariñas Del Cerro
Abstract Argumentation And Answer Set Programming: Two Faces Of Nelson’S Logic, Jorge Fandinno, Luis Fariñas Del Cerro
Computer Science Faculty Publications
In this work, we show that both logic programming and abstract argumentation frameworks can be interpreted in terms of Nelson’s constructive logic N4. We do so by formalising, in this logic, two principles that we call noncontradictory inference and strengthened closed world assumption: the first states that no belief can be held based on contradictory evidence while the latter forces both unknown and contradictory evidence to be regarded as false. Using these principles, both logic programming and abstract argumentation frameworks are translated into constructive logic in a modular way and using the object language. Logic programming implication and abstract argumentation …
Logic Programs Vs. First-Order Formulas In Textual Inference, Yuliya Lierler, Vladimir Lifschitz
Logic Programs Vs. First-Order Formulas In Textual Inference, Yuliya Lierler, Vladimir Lifschitz
Computer Science Faculty Proceedings & Presentations
In the problem of recognizing textual entailment, the goal is to decide, given a text and a hypothesis expressed in a natural language, whether a human reasoner would call the hypothesis a consequence of the text. One approach to this problem is to use a first-order reasoning tool to check whether the hypothesis can be derived from the text conjoined with relevant background knowledge, after expressing all of them by first-order formulas. Another possibility is to express the hypothesis, the text, and the background knowledge in a logic programming language, and use a logic programming system. We discuss the relation …
On The Relation Of Constraint Answer Set Programming Languages And Algorithms, Yuliya Lierler
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 …
Termination Of Grounding Is Not Preserved By Strongly Equivalent Transformations, Yuliya Lierler, Vladimir Lifschitz
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.
One More Decidable Class Of Finitely Ground Programs, Yuliya Lierler, Vladimir Lifschitz
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.
Head-Elementary-Set-Free Logic Programs, Martin Gebser, Joohyung Lee, Yuliya Lierler
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
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 …
Automatic Compilation Of Protocol Insecurity Problems Into Logic Programming, Alessandro Armondo, Luca Compagna, Yuliya Lierler
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.