The aggregates have greatly extended the representation power, in both theory and practice, of Answer Set programming. Significant understanding of programs with aggregates has been gained in the last decade. However,...
详细信息
The aggregates have greatly extended the representation power, in both theory and practice, of Answer Set programming. Significant understanding of programs with aggregates has been gained in the last decade. However, there is still a substantial difficulty in understanding the semantics due to the nonmonotonic behavior of aggregates, which is demonstrated by several distinct semantics for aggregates in the existing work. In this paper, we aim to understand these distinct semantics in a more uniform way. Particularly, by satisfiability, rationality and consistency principles, we are able to give a uniform and simple characterizations of the three major distinct types of answer set semantics.
The theory of strings with concatenation has been widely argued as the basis of constraint solving for verifying string-manipulating programs. However, this theory is far from adequate for expressing many string const...
详细信息
The theory of strings with concatenation has been widely argued as the basis of constraint solving for verifying string-manipulating programs. However, this theory is far from adequate for expressing many string constraints that are also needed in practice;for example, the use of regular constraints (pattern matching against a regular expression), and the string-replace function (replacing either the first occurrence or all occurrences of a "pattern" string constant/variable/regular expression by a "replacement" string constant/variable), among many others. Both regular constraints and the string-replace function are crucial for such applications as analysis of JavaScript (or more generally HTML5 applications) against cross-site scripting (XSS) vulnerabilities, which motivates us to consider a richer class of string constraints. The importance of the string-replace function (especially the replace-all facility) is increasingly recognised, which can be witnessed by the incorporation of the function in the input languages of several string constraint solvers. Recently, it was shown that any theory of strings containing the string-replace function (even the most restricted version where pattern/replacement strings are both constant strings) becomes undecidable if we do not impose some kind of straight-line (aka acyclicity) restriction on the formulas. Despite this, the straight-line restriction is still practically sensible since this condition is typically met by string constraints that are generated by symbolic execution. In this paper, we provide the first systematic study of straight-line string constraints with the string-replace function and the regular constraints as the basic operations. We show that a large class of such constraints (i.e. when only a constant string or a regular expression is permitted in the pattern) is decidable. We note that the string-replace function, even under this restriction, is sufficiently powerful for expressing the concatenation o
Recent advances in knowledge compilation introduced techniques to compile positive logic programs into propositional logic, essentially exploiting the constructive nature of the least fixpoint computation. This approa...
详细信息
Recent advances in knowledge compilation introduced techniques to compile positive logic programs into propositional logic, essentially exploiting the constructive nature of the least fixpoint computation. This approach has several advantages over existing approaches: it maintains logical equivalence, does not require (expensive) loop-breaking preprocessing or the introduction of auxiliary variables, and significantly outperforms existing algorithms. Unfortunately, this technique is limited to negation-free programs. In this paper, we show how to extend it to general logic programs under the well-founded semantics. We develop our work in approximation fixpoint theory, an algebraical framework that unifies semantics of different logics. As such, our algebraical results are also applicable to autoepistemic logic, default logic and abstract dialectical frameworks.
Martingale theory yields a powerful set of tools that have recently been used to prove quantitative properties of stochastic systems such as stochastic safety and qualitative properties such as almost sure termination...
详细信息
ISBN:
(纸本)9783662496749;9783662496732
Martingale theory yields a powerful set of tools that have recently been used to prove quantitative properties of stochastic systems such as stochastic safety and qualitative properties such as almost sure termination. In this paper, we examine proof techniques for establishing almost sure persistence and recurrence properties of infinite-state discrete time stochastic systems. A persistence property lozenge square (P) specifies that almost all executions of the stochastic system eventually reach P and stay there forever. Likewise, a recurrence property square lozenge(Q) specifies that a target set Q is visited infinitely often by almost all executions of the stochastic system. Our approach extends classic ideas on the use of Lyapunov-like functions to establish qualitative persistence and recurrence properties. Next, we extend known constraint-based invariant synthesis techniques to deduce the necessary supermartingale expressions to partly mechanize such proofs. We illustrate our techniques on a set of interesting examples.
Today'smaintenance workforce operates in a complex business environment and relies onmetrics that indirectly link equipment breakdown, fluctuating production rate, demand uncertainties and fluctuating raw material...
详细信息
Today'smaintenance workforce operates in a complex business environment and relies onmetrics that indirectly link equipment breakdown, fluctuating production rate, demand uncertainties and fluctuating raw material requirements. This has triggered a change in the scope as well as the substance of maintenance workforce theory and practice, and the necessary requirement to promote a full understanding of maintenance workforce optimization of some seemingly non-polynomial hard problems. Theorizing is essential on the near optimal solution techniques for the maintenance workforce problem. In this paper, a fuzzy goal programming model is proposed and used in formulating a single objective function for maintenance workforce optimization with stochastic constraint consideration. The performance of the proposed model was verified using data obtained from a production system and simulated annealing (SA) as a solution method. The results obtained using SA and differential evolution (DE) were compared on the basis of computational time and quality of solution. We observed that the SA results outperform those of the DE algorithm. Based on the results obtained, the proposed model has the capacity to generate reliable information for preventive and breakdown workforce maintenance planning.
As the notions of Agency and Multiagent System became important topics for the Computer Science and Artificial Intelligence communities, Agent programming has been proposed as a paradigm for the development of compute...
详细信息
As the notions of Agency and Multiagent System became important topics for the Computer Science and Artificial Intelligence communities, Agent programming has been proposed as a paradigm for the development of computer systems. As such, in the last decade, we have seen the flourishing of the literature on Agent programming with the proposal of several programming languages, e.g. AgentSpeak (RAO, 1996; BORDINI; HUBNER;WOOLDRIDGE, 2007), Jadex (POKAHR; BRAUBACH; LAMERSDORF, 2005), JACK (HOWDEN et al., 2001), 3APL/2APL (DASTANI; VAN RIEMSDIJK; MEYER, 2005; DASTANI, 2008), GOAL (HINDRIKS et al., 2001), among others. Agent programming is a programming paradigm proposed by Shoham (1993) in which the minimal units are agents. An agent is an entity composed of mental attitudes, that describe the its internal state - such as its motivations and decisions - as well as its relation to the external world - its beliefs about the world, its obligations, etc. This programming paradigm stems from the work on Philosophy of Action and Artificial Intelligence concerning the notions of intentional action and formal models of agents’ mental states. As such, the meaning (and properties) of notions such as belief, desire, intention, etc. as studied in these disciplines are of central importance to the area. Particularly, we will concentrate in our work on agent programming languages influenced by the so-called BDI paradigm of agency, in which an agent is described by her beliefs, desires, intentions. While the engineering of such languages has been much discussed, the connections between the theoretical work on Philosophy and Artificial Intelligence and its implementations in programming languages are not so clearly understood yet. This distance between theory and practice has been acknowledged in the literature for agent programming languages and is commonly known as the “semantic gap”. Many authors have attempted to tackle this problem for different programming languages, as for the ca
Software testing is one of the most popular validation techniques in the software industry. Surprisingly, we can only find a few approaches to testing in the context of logicprogramming. In this paper, we introduce a...
详细信息
Software testing is one of the most popular validation techniques in the software industry. Surprisingly, we can only find a few approaches to testing in the context of logicprogramming. In this paper, we introduce a systematic approach for dynamic testing that combines both concrete and symbolic execution. Our approach is fully automatic and guarantees full path coverage when it terminates. We prove some basic properties of our technique and illustrate its practical usefulness through a prototype implementation.
Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and anal...
详细信息
Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates.
Partial functions are common abstractions in formal specification notations such as Z, B and Alloy. Conversely, executable programming languages usually provide little or no support for them. In this paper we propose ...
详细信息
Partial functions are common abstractions in formal specification notations such as Z, B and Alloy. Conversely, executable programming languages usually provide little or no support for them. In this paper we propose to add partial functions as a primitive feature to a Constraint logicprogramming (CLP) language, namely {log}. Although partial functions could be programmed on top of {log}, providing them as first-class citizens adds valuable flexibility and generality to the form of set-theoretic formulas that the language can safely deal with. In particular, the paper shows how the {log} constraint solver is naturally extended in order to accommodate for the new primitive constraints dealing with partial functions. Efficiency of the new version is empirically assessed by running a number of non-trivial set-theoretical goals involving partial functions, obtained from specifications written in Z.
暂无评论