We present a new execution strategy for constraint logic programs called Failure Tabled CLP. Similarly to Tabled CLP our strategy records certain derivations in order to prune further derivations. However, our method ...
详细信息
We present a new execution strategy for constraint logic programs called Failure Tabled CLP. Similarly to Tabled CLP our strategy records certain derivations in order to prune further derivations. However, our method only learns from failed derivations. This allows us to compute interpolants rather than constraint projection for generation of reuse conditions. As a result, our technique can be used where projection is too expensive or does not exist. Our experiments indicate that Failure Tabling can speed up the execution of programs with many redundant failed derivations as well as achieve termination in the presence of infinite executions.
We consider disjunctive logic programs without function symbols but with existential quantification in rule heads, under the semantics of general stable models. There are at least two interesting prospects in these pr...
详细信息
We consider disjunctive logic programs without function symbols but with existential quantification in rule heads, under the semantics of general stable models. There are at least two interesting prospects in these programs. The first is that a program can be made more succinct by using existential variables, and the second is on the potential in representing defeasible ontological knowledge by these logic programs. This paper studies some of the properties of these programs. First, we show a simple yet intuitive definition of stable models for these programs that does not resort to second-order logic. Second, the stable models of these programs can be characterized by an extension of progression for disjunctive programs, which provides a native characterization of justification for stable models. We then study the decidability issue. While the stable model existence problem for safe disjunctive programs is decidable, with existential quantification allowed in rule heads the problem becomes undecidable. We identify an interesting decidable fragment by exploring a new notion of stratification over existential quantification.
Several extensions of the stable model semantics are available to describe "intensional" functions-functions that can be described in terms of other functions and predicates by logic programs. Such functions...
详细信息
Several extensions of the stable model semantics are available to describe "intensional" functions-functions that can be described in terms of other functions and predicates by logic programs. Such functions are useful for expressing inertia and default behaviors of systems, and can be exploited for alleviating the grounding bottleneck involving functional fluents. However, the extensions were defined in different ways under different intuitions. In this paper we provide several reformulations of the extensions, and note that they are in fact closely related to each other and coincide on large syntactic classes of logic programs.
We present a method for the automated verification of temporal properties of infinite state systems. Our verification method is based on the specialization of constraint logic programs (CLP) and works in two phases: (...
详细信息
We present a method for the automated verification of temporal properties of infinite state systems. Our verification method is based on the specialization of constraint logic programs (CLP) and works in two phases: (1) in the first phase, a CLP specification of an infinite state system is specialized with respect to the initial state of the system and the temporal property to be verified, and (2) in the second phase, the specialized program is evaluated by using a bottom-up strategy. The effectiveness of the method strongly depends on the generalization strategy which is applied during the program specialization phase. We consider several generalization strategies obtained by combining techniques already known in the field of program analysis and program transformation, and we also introduce some new strategies. Then, through many verification experiments, we evaluate the effectiveness of the generalization strategies we have considered. Finally, we compare the implementation of our specialization-based verification method to other constraint-based model checking tools. The experimental results show that our method is competitive with the methods used by those other tools.
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and Constraint...
详细信息
Dealing with domains involving substantial quantitative information in Answer Set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and Constraint programming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. This goes against central knowledge representation principles that contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed with the ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. The applicability of ASP{f} is demonstrated by a case study on an actual industrial application.
A large body of work has been dedicated to termination analysis of logic programs but relatively little has been done to analyze non-termination. In our opinion, explaining non-termination is a much more important tas...
详细信息
A large body of work has been dedicated to termination analysis of logic programs but relatively little has been done to analyze non-termination. In our opinion, explaining non-termination is a much more important task because it can dramatically improve a user's ability to effectively debug large, complex logic programs without having to abide by punishing syntactic restrictions. Non-termination analysis examines program execution history when the program is suspected to not terminate and informs the programmer about the exact reasons for this behavior. In Liang and Kifer (2013), we studied the problem of non-termination in tabled logic engines with subgoal abstraction, such as XSB, and proposed a suite of algorithms for non-termination analysis, called Terminyzer. These algorithms analyze forest logging traces and output sequences of tabled subgoal calls that are the likely causes of non-terminating cycles. However, this feedback was hard to use in practice: the same subgoal could occur in multiple rule heads and in even more places in rule bodies, so Terminyzer left too much tedious, sometimes combinatorially large amount of work for the user to do manually. Here we propose a new suite of algorithms, Terminyzer(+), which closes this usability gap. Terminyzer+ can detect not only sequences of subgoals that cause non-termination, but, importantly, the exact rules where they occur and the rule sequences that get fired in a cyclic manner, thus causing non-termination. This makes Terminyzer(+) suitable as a back-end for user-friendly graphical interfaces on top of Terminyzer(+), which can greatly simplify the debugging process. Terminyzer(+) back-ends exist for the SILK system as well as for the open-source Flora-2 system. A graphical interface has been developed for SILK and is currently underway for Flora-2. We also report experimental studies, which confirm the effectiveness of Terminyzer(+) on a host of large real-world knowledge bases. All tests used in this pape
Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we s...
详细信息
Maher (2012) introduced an approach for relative expressiveness of defeasible logics, and two notions of relative expressiveness were investigated. Using the first of these definitions of relative expressiveness, we show that all the defeasible logics in the DL framework are equally expressive under this formulation of relative expressiveness. The second formulation of relative expressiveness is stronger than the first. However, we show that logics incorporating individual defeat are equally expressive as the corresponding logics with team defeat. Thus the only differences in expressiveness of logics in DL arise from differences in how ambiguity is handled. This completes the study of relative expressiveness in DL begun in Maher (2012).
In this paper we take on Stuart C. Shapiro's challenge of solving the Jobs Puzzle automatically and do this via controlled natural language processing. Instead of encoding the puzzle in a formal language that migh...
详细信息
In this paper we take on Stuart C. Shapiro's challenge of solving the Jobs Puzzle automatically and do this via controlled natural language processing. Instead of encoding the puzzle in a formal language that might be difficult to use and understand, we employ a controlled natural language as a high-level specification language that adheres closely to the original notation of the puzzle and allows us to reconstruct the puzzle in a machine-processable way and add missing and implicit information to the problem description. We show how the resulting specification can be translated into an answer set program and be processed by a state-of-the-art answer set solver to find the solutions to the puzzle.
We study the problem of finding optimal plans for multiple teams of robots through a mediator, where each team is given a task to complete in its workspace on its own and where teams are allowed to transfer robots bet...
详细信息
We study the problem of finding optimal plans for multiple teams of robots through a mediator, where each team is given a task to complete in its workspace on its own and where teams are allowed to transfer robots between each other, subject to the following constraints: 1) teams (and the mediator) do not know about each other's workspace or tasks (e.g., for privacy purposes);2) every team can lend or borrow robots, but not both (e.g., transportation/calibration of robots between/for different workspaces is usually costly). We present a mathematical definition of this problem and analyze its computational complexity. We introduce a novel, logic-based method to solve this problem, utilizing action languages and answer set programming for representation, and the state-of-the-art ASP solvers for reasoning. We show the applicability and usefulness of our approach by experiments on various scenarios of responsive and energy-efficient cognitive factories.
In this paper, we combine Answer Set programming (ASP) with Dynamic Linear Time Temporal logic (DLTL) to define a temporal logicprogramming language for reasoning about complex actions and infinite computations. DLTL...
详细信息
暂无评论