Search

Abstract: In this paper we investigate the use of classical logic as a basis for instantiating abstract argumentation frameworks. In the first part, we propose desirable properties of attack relations in the form of postulates and classify several well-known attack relations from the literature with regards to the satisfaction of these postulates. Furthermore, we provide additional postulates that help us prove characterisation results for these attack relations. In the second part of the paper, we present postulates regarding the logical content of extensions of argument graphs that may be constructed with classical logic. We then conduct a comprehensive study of the status of these postulates in the context of the various combinations of attack relations and extension semantics. [Copyright &y& Elsevier]

This paper proposes a new theoretic approach to a specific interaction of continuous and discrete dynamics in switched control systems known as a Zeno behaviour. We study executions of switched control systems with affine structure that admit infinitely many discrete transitions on a finite time interval. Although the real world processes do not present the corresponding behaviour, mathematical models of many engineering systems may be Zeno due to the used formal abstraction. We propose two useful approximative approaches to the Zeno dynamics, namely, an analytic technique and a variational description of this phenomenon. A generic trajectory associated with the Zeno dynamics can finally be characterized as a result of a specific projection or/and an optimization procedure applied to the original dynamic model. The obtained analytic and variational techniques provide an effective methodology for constructive approximations of the general Zeno-type behaviour. We also discuss shortly some possible applications of the proposed approximation schemes. [ABSTRACT FROM AUTHOR]

Real-time systems (RTS) are omnipresent in several domains. The trend is to use multiprocessor architecture to satisfy the timing constraints of such systems. The model-checking methods have proven to be useful for making the development process reliable at a high abstraction level. Based on this approach, the present paper proposes a new technique for scheduling analysis of a partitioned multiprocessor RTS. Starting from a model with dynamic priority time Petri Nets modeling the system, we have proposed a generation of a reduced states graph. Thus, through the properties of the graph the schedulability is checked. Our approach provides an implementation of a Partition Checker tool, which produces an affirmation of the schedulability or a counterexample in the case of non-schedulable system to reduce the SW/HW space exploration. [ABSTRACT FROM AUTHOR]

Abstract: The study of arguments as abstract entities and their interaction as introduced by Dung (1995) has become one of the most active research branches within Artificial Intelligence and Reasoning. A main issue for abstract argumentation systems is the selection of acceptable sets of arguments. Value-based argumentation, as introduced by Bench-Capon (2003) , extends Dungʼs framework. It takes into account the relative strength of arguments with respect to some ranking representing an audience: an argument is subjectively accepted if it is accepted with respect to some audience, it is objectively accepted if it is accepted with respect to all audiences. Deciding whether an argument is subjectively or objectively accepted, respectively, are computationally intractable problems. In fact, the problems remain intractable under structural restrictions that render the main computational problems for non-value-based argumentation systems tractable. In this paper we identify nontrivial classes of value-based argumentation systems for which the acceptance problems are polynomial-time tractable. The classes are defined by means of structural restrictions in terms of the underlying graphical structure of the value-based system. Furthermore we show that the acceptance problems are intractable for two classes of value-based systems that where conjectured to be tractable by Dunne (2007) . [Copyright &y& Elsevier]

Abstract: Partial transition systems support abstract model checking of complex temporal properties by combining both over- and under-approximating abstractions into a single model. Over the years, three families of such modeling formalisms have emerged, represented by (1) Kripke Modal Transition Systems (KMTSs), with restrictions on necessary and possible behaviors; (2) Mixed Transition Systems (MixTSs), with relaxation on these restrictions; and (3) Generalized Kripke MTSs (GKMTSs), with hyper-transitions, respectively. In this paper, we investigate these formalisms based on two fundamental ways of using partial transition systems (PTSs) – as objects for abstracting concrete systems (and thus, a PTS is semantically consistent if it abstracts at least one concrete system) and as models for checking temporal properties (and thus, a PTS is logically consistent if it gives consistent interpretation to all temporal logic formulas). We study the connection between semantic and logical consistency of PTSs, compare the three families w.r.t. their expressive power (i.e., what can be modeled, what abstractions can be captured using them), and discuss the analysis power of these formalisms, i.e., the cost and precision of model checking. Specifically, we identify a class of PTSs for which semantic and logical consistency coincide and define a necessary and sufficient structural condition to guarantee consistency. We also show that all three families of PTSs have the same expressive power (but do differ in succinctness). However, GKMTSs are more precise (i.e., can establish more properties) for model checking than the other two families. The direct use of GKMTSs in practice has been hampered by the difficulty of encoding them symbolically. We address this problem by developing a new semantics for temporal logic of PTSs that makes the MixTS family as precise for model checking as the GKMTS family. The outcome is a symbolic model checking algorithm that combines the efficient encoding of MixTSs with the model checking precision of GKMTSs. Our preliminary experiments indicate that the new algorithm is a good match for predicate-abstraction-based model checkers. [Copyright &y& Elsevier]

Abstract: One of the fundamental human cognitive processes is problem solving. As a higher-layer cognitive process, problem solving interacts with many other cognitive processes such as abstraction, searching, learning, decision making, inference, analysis, and synthesis on the basis of internal knowledge representation by the object–attribute-relation (OAR) model. Problem solving is a cognitive process of the brain that searches a solution for a given problem or finds a path to reach a given goal. When a problem object is identified, problem solving can be perceived as a search process in the memory space for finding a relationship between a set of solution goals and a set of alternative paths. This paper presents both a cognitive model and a mathematical model of the problem solving process. The cognitive structures of the brain and the mechanisms of internal knowledge representation behind the cognitive process of problem solving are explained. The cognitive process is formally described using real-time process algebra (RTPA) and concept algebra. This work is a part of the cognitive computing project that designed to reveal and simulate the fundamental mechanisms and processes of the brain according to Wang’s layered reference model of the brain (LRMB), which is expected to lead to the development of future generation methodologies for cognitive computing and novel cognitive computers that are capable of think, learn, and perceive. [Copyright &y& Elsevier]

Abstract-Unification grammars are widely used for encoding human knowledge. For unification systems, one major difficulty is the debugging of rules. In this paper, the authors suggest a novel method based on model checking to theoretically verify a complex grammar system for a unification-based parser. We propose the modeling method of the grammar and, more importantly, the abstraction method to compress the state space. We apply partial Kripke structures to model the rules. We prove that the state space can be reduced by several orders of magnitude while still keeping the behaviors of a noncompressed one. Practical verification issues are discussed, including the restrictions on specifications, the properties to check, etc. The proposed method will contribute to the effective debugging and application of unification grammars. [ABSTRACT FROM AUTHOR]

This paper presents a compositional method with failure- preserving abstraction for scalable asynchronous design verification. It combines efficient state-space reductions and novel interface refinement and can dramatically reduce the complexity of state space while decreasing the introduction of false failures. This allows much larger designs to be verified as demonstrated in the experimental results. [ABSTRACT FROM AUTHOR]

This paper describes methods for automatically analyzing formal, state-based requirements specifications for some aspects of completeness and consistency. The approach uses a low-level functional formalism, simplifying the analysis process. State-space explosion problems are eliminated by applying the analysis at a high level of abstraction; i.e., instead of generating a reachability graph for analysis, the analysis is performed directly on the model. The method scales up to large systems by decomposing the specification into smaller, analyzable parts and then using functional composition rules to ensure that verified properties hold for the entire specification. The analysis algorithms and tools have been validated on TCAS II, a complex, airborne, collision-avoidance system required on all commercial aircraft with more than 30 passengers that fly in U.S. airspace. [ABSTRACT FROM AUTHOR]