On principle-based evaluation of extension-based argumentation semantics

The increasing variety of semantics proposed in the context of Dung's theory of argumentation makes more and more inadequate the example-based approach commonly adopted for evaluating and comparing different semantics. To fill this gap, this paper provides two main contributions. First, a set of general criteria for semantics evaluation is introduced by proposing a formal counterpart to several intuitive notions related to the concepts of maximality, defense, directionality, and skepticism. Then, the proposed criteria are applied in a systematic way to a representative set of argumentation semantics available in the literature, namely grounded, complete, preferred, stable, semi-stable, ideal, prudent, and CF2 semantics.     

An invitation to Friendly Testing

1IntroductionSinceitspresentationin[1,2]TestingSemanticshasbeenwidelystudiedandusedasanaturalwaytodefineanobservationalbehaviorwithareasonablepowertodistinguishsemanticallydifferentprocesses.TestingSemanticsisdefinedbyobservingtheoperationalsemanticsofprocessesbymeansoftests.Testsarejustprocesseswhichmayexecuteanewactionwreportingsuccessofthetestapplication.Todefinetheapplicationofatesttoaprocesslweconsiderthedifferentcomputationsoftheexperimentalsystemwhichisobtainedbycomposinginparallelthe…     

Defeasible inheritance with doubt index and its axiomatic characterization

This article introduces and uses a representation of defeasible inheritance networks where links in the network are viewed as propositions, and where defeasible links are tagged with a quantitative indication of the proportion of exceptions, called the doubt index. This doubt index is used for restricting the length of the chains of inference.The representation also introduces the use of defeater literals that disable the chaining of subsumption links. The use of defeater literals replaces the use of negative defeasible inheritance links, expressing “most A are not B”. The new representation improves the expressivity significantly.Inference in inheritance networks is defined by a combination of axioms that constrain the contents of network extensions, a heuristic restriction that also has that effect, and a nonmonotonic operation of minimizing the set of defeater literals while retaining consistency.We introduce an underlying semantics that defines the meaning of literals in a network, and prove that the axioms are sound with respect to this semantics. We also discuss the conditions for obtaining completeness.Traditional concepts, assumptions and issues in research on nonmonotonic or defeasible inheritance are reviewed in the perspective of this approach.     

What is a free name in a process algebra?

There are two popular approaches to specifying the semantics of process algebras: labelled transition semantics and reaction semantics. While the notion of free name is rather unproblematic for labelled transition semantics this is not so for reaction semantics in the presence of a structural congruence for unfolding recursive declarations.We show that the standard definition of free name is not preserved under the structural congruence. We then develop a fixed point approach to the set of free names and show that it is invariant under the structural congruence.     

Query containment under bag and bag-set semantics

Conjunctive queries (CQs) are at the core of query languages encountered in many logic-based research fields such as AI, or database systems. The majority of existing work assumes set semantics but often in real applications the manipulation of duplicate tuples is required. One of the major problems that arises as part of advanced features of query optimization, data integration, query reformulation and many other research topics is testing for containment of such queries. In this work, we investigate the complexity of query containment problem for CQs under bag semantics (i.e. duplicate tuples are allowed in both the database and the results of queries) and under bag-set semantics (i.e. duplicates are allowed in the result of the queries but not in the database). We derive complexity results for these problems for five major subclasses of CQs; and we also find necessary conditions for CQ query containment. The general case of these problems remains open.     

A formal library of set relations and its application to synchronous languages

Set relations are particularly suitable for specifying the small-step operational semantics of synchronous languages. In this paper, a formal library of set relations for the definition, verification of properties, and execution of binary set relations is presented. The formal library consists of a set of theories written in the Prototype Verification System (PVS) that contains definitions and proofs of properties, such as determinism and compositionality, for synchronous relations. The paper also proposes a serialization procedure that enables the simulation of synchronous set relations via set rewriting systems. The library and the serialization procedure are illustrated with the rewriting logic semantics of the Plan Execution Interchange Language (PLEXIL), a rich synchronous plan execution language developed by NASA to support autonomous spacecraft operations.     

Maximal traces and path-based coalgebraic temporal logics

This paper gives a general coalgebraic account of temporal logics whose semantics involves a notion of computation path. Examples of such logics include the logic CTL* for transition systems and the logic PCTL for probabilistic transition systems. Our path-based temporal logics are interpreted over coalgebras of endofunctors obtained as the composition of a computation type (e.g. non-deterministic or stochastic) with a general transition type. The semantics of such logics relies on the existence of execution maps similar to the trace maps introduced by Jacobs and co-authors as part of the coalgebraic theory of finite traces (Hasuo et al., 2007 [1]). We consider finite execution maps derived from the theory of finite traces, and a new notion of maximal execution map that accounts for maximal, possibly infinite executions. The latter is needed to recover the logics CTL* and PCTL as specific path-based logics.     

Selecting informative features with fuzzy-rough sets and its application for complex systems monitoring

One of the main obstacles facing current intelligent pattern recognition applications is that of dataset dimensionality. To enable these systems to be effective, a redundancy-removing step is usually carried out beforehand. Rough set theory (RST) has been used as such a dataset pre-processor with much success, however it is reliant upon a crisp dataset; important information may be lost as a result of quantisation of the underlying numerical features. This paper proposes a feature selection technique that employs a hybrid variant of rough sets, fuzzy-rough sets, to avoid this information loss. The current work retains dataset semantics, allowing for the creation of clear, readable fuzzy models. Experimental results, of applying the present work to complex systems monitoring, show that fuzzy-rough selection is more powerful than conventional entropy-, PCA- and random-based methods.     

The ubiquity of discovery

As scientists interested in studying the phenomenon of “intelligence”, we first choose a view of Man, develop a theory of how intelligent behavior is managed, and construct some models which can test and refine that theory. The view we choose is that Man is a processor of symbolic information. The theory is that sophisticated cognitive tasks can be cast as searches or explorations, and that each human possesses (and efficiently accesses) a large body of informal rules of thumb (or heuristics) which constrain his search. The source of what we colloquially call “intelligence” is seen to be very efficient searching of an a priori immense space. Some computational models which incorporate this theory are described. Among them is AM, a computer program that develops new mathematical concepts and formulates conjectures involving them; AM is guided in this exploration by a collection of 250 more or less general heuristic rules. The operational nature of such models allows experiments to be performed upon them, experiments which help us test and develop hypotheses about intelligence. One interesting finding has been the ubiquity of this kind of heuristic guidance: intelligence permeates everyday problem solving and invention, as well as the kind of problem solving and invention that scientists and artists perform. The ultimate goals of this kind of research are (i) to de-mystify the process by which new science and art are created, and (ii) to build tools (computer programs) which enhance man's mental capabilities.     

粒及粒计算在逻辑推理中的应用

讨论了信息粒的结构及其实例。基于Rough集方法定义了决策规则粒,构造了决策规则粒库,它被用作逻辑推理。定义了粒语言,描述了这种语言的语法、语义、粒语句的运算法则和粒之相关的几个性质。定义了粒之间的相互包含(inclusion)和相似(closeness)。基于这些概念,构造了一种逻辑推理的新模型。这种推理模式的特点在于它既是逻辑的又是集合论的。所谓逻辑的就是说推理是遵循一种逻辑运算;所谓集合论的是指这种推理可利用对应于这种逻辑公式的意义集的运算进行推理,还用实例说明了这种推理模式是可行和有效的。     

On stratified disjunctive programs

We address the problem of a consistent fixpoint semantics for general disjunctive programs restricted to stratifiable programs which do not recurse through negative literals. We apply the nonmonotonic fixpoint theory developed by Apt, Blair and Walker to a closure operatorT ^c and develop a fixpoint semantics for stratified disjunctive programs. We also provide an iterative definition for negation, called the Generalized Closed World Assumption for Stratified programs (GCWAS), and show that our semantics captures this definition. We develop a model-theoretic semantics for stratified disjunctive programs and show that the least state characterized by the fixpoint semantics corresponds to a stable-state defined in a manner similar to the stable-models of Gelfond and Lifschitz. We also discuss a weaker stratification semantics for general disjunctive programs based on the Weak Generalized Closed World Assumption.     

Logic programs with abstract constraint atoms: The role of computations

We provide a new perspective on the semantics of logic programs with arbitrary abstract constraints. To this end, we introduce several notions of computation. We use the results of computations to specify answer sets of programs with constraints. We present the rationale behind the classes of computations we consider, and discuss the relationships among them. We also discuss the relationships among the corresponding concepts of answer sets. One of those concepts has several compelling characterizations and properties, and we propose it as the correct generalization of the answer-set semantics to the case of programs with arbitrary constraints. We show that several other notions of an answer set proposed in the literature for programs with constraints can be obtained within our framework as the results of appropriately selected classes of computations.     

Equivalence of queries that are sensitive to multiplicities

The query equivalence problem has been studied extensively for set-semantics and, more recently, for bag and bag-set semantics. However, SQL queries often combine set, bag and bag-set semantics. For example, an SQL query that returns a multiset of elements may call a subquery or view that returns a set of elements. Queries may access both relations that do not contain duplicates, as well as relations with duplicates. As another example, in SQL one can compute a multiset-union of queries, each of which returns a set of answers. This paper presents combined semantics, which formally models query evaluation combining set, bag and bag-set semantics. The equivalence problem for queries evaluated under combined semantics is studied. A sufficient condition for equivalence is presented. For several important common classes of queries necessary and sufficient conditions for equivalence are presented. An early version of this article appeared in [7]. This paper extends [7] to include bag semantics, in addition to set and bag-set semantics. This work was partially supported by the Israel Science Foundation (Grant 1032/05).     

Set based logic programming

In a previous paper (Blair et al. 2001), the authors showed that the mechanism underlying Logic Programming can be extended to handle the situation where the atoms are interpreted as subsets of a given space X. The view of a logic program as a one-step consequence operator along with the concepts of supported and stable model can be transferred to such situations. In this paper, we show that we can further extend this paradigm by creating a new one-step consequence operator by composing the old one-step consequence operator with a monotonic idempotent operator (miop) in the space of all subsets of X, 2 ^X . We call this extension set based logic programming. We show that such a set based formalism for logic programming naturally supports a variety of options. For example, if the underlying space has a topology, one can insist that the new one-step consequence operator always produces a closed set or always produces an open set. The flexibility inherent in the semantics of set based logic programs is due to both the range of natural choices available for specifying the semantics of negation, as well as the role of monotonic idempotent operators (miops) as parameters in the semantics. This leads to a natural type of polymorphism for logic programming, i.e. the same logic program can produce a variety of outcomes depending on the miop associated with the semantics. We develop a general framework for set based programming involving miops. Among the applications, we obtain integer-based representations of real continuous functions as stable models of a set based logic program.      

On the composability of consistency conditions

This paper presents a formal framework, which is based on the notion of a serialization set, that enables to compose a set of consistency conditions into a more restrictive one. To exemplify the utility of this framework, a list of very basic consistency conditions is identified, and it is shown that various compositions of the basic conditions yield some of the most commonly used consistency conditions, such as sequential consistency, causal memory, and Pipelined RAM. The paper also lists several applications that can benefit from even weaker semantics than Pipelined RAM that can be expressed as a composition of a small subset of the basic conditions.     

Abstract interpretation of resolution-based semantics

We extend the abstract interpretation point of view on context-free grammars by Cousot and Cousot to resolution-based logic programs and proof systems. Starting from a transition-based small-step operational semantics of Prolog programs (akin to the Warren Machine), we consider maximal finite derivations for the transition system from most general goals. This semantics is abstracted by instantiation to terms and furthermore to ground terms, following the so-called c- and s-semantics approach. Orthogonally, these sets of derivations can be abstracted to SLD-trees, call patterns and models, as well as interpreters providing effective implementations (such as Prolog). These semantics can be presented in bottom–up fixpoint form. This abstract interpretation-based construction leads to classical bottom–up semantics (such as the s-semantics of computed answers, the c-semantics of correct answers of Keith Clark, and the minimal-model semantics of logical consequences of Maarten van Emden and Robert Kowalski). The approach is general and can be applied to infinite and top–down semantics in a straightforward way.     

Coverage and invariability by structural functions

Based on some of the results and definitions provided in the article System linkage: Structural functions and hierarchies (Lloret et al. “System linkage: structural functions and hierarchies”, Cybern. Syst. Int. J., 29, pp. 35–46, 1998) and adding new definitions that are in keeping with the spirit of the same article, new results have been obtained that explore the utility of the structural input–output function (also transferable to the other structural functions) and that expand on studies conducted to date on variables (cells).

Our approach is based principally on the application of graph theory to the study of relationships between variables (cells) using specific set theory concepts, introducing new definitions and adapting continuous function properties to our discrete environment. More specifically, we present two new concepts—coverage between sets and the invariant set—analysing their inter-relatedness from the perspective of structural functions, i.e. from the point of view of influences in the system. To date these concepts have been handled from a continuous point of view, and so the discrete approach described here will lay the foundations for new developments in this direction.

Although the development of the concepts may, a priori, appear to very theoretical, they are, in fact, much more practical than would appear to be the case. A result such as the fact that A covers B, for example, can be interpreted in terms of the latter set being formed of direct influences from elements in the former set in relation to one or more than one relationships. Analogously, the invariant set concept may be interpreted as the set maintaining its structure and status, remaining constant with respect to any possible relationships.