68538
Complexity Results for Restricted Credulous Default Reasoning
This paper concentrates on the complexity of the decision problem deciding whether a literal belongs to at least one extension of a default theory 〈D,W〉 in which D is a set of Horn defaults and W is a definite Horn formula or a BidHorn formula.
8163164
Regular disjunction-free default theories
In this paper, the class of regular disjunction-free default theories is introduced and investigated. A transformation from regular default theories to normal default theories is established. The initial theory and the transformed theory have the same extensions when restricted to old variables. Hence, regular default theories enjoy some similar properties (e.g., existence of extensions, semi-monotonicity) as normal default theories. Then, a new algorithm for credulous reasoning of regular theories is developed. This algorithm runs in a time not more thanO(1. 45n), wheren is the number of defaults. In case of regular prerequisite-free or semi-2CNF default theories, the credulous reasoning can be solved in polynomial time. However, credulous reasoning for semi-Horn default theories is shown to be NP-complete although it is tractable for Horn default theories. Moreover, skeptical reasoning for regular unary default theories is co-NP-complete.
30011892
Complexity of argument-based default reasoning with specificity
In this paper we investigate the complexity of Dung and Son's approach to default reasoning with specificity. We show that the three decision problems: existence of extensions, brave reasoning and cautious reasoning are generally complete for the second level of the polynomial hierarchy. For some restricted cases, e.g., Horn and 2CNF default theories, all the three problems are intractable although classical brave reasoning in these cases is tractable. Finally, we show that stratification can not reduce the complexity of brave and cautious reasoning although it guarantees the existence of extensions.
33218482
Some Algorithms for Extension Computation of Nonmonotonic Rule Systems
In this paper, we will place our emphasis on the problem of existence of extensions and on finding more efficient algorithms for computing extensions of nonmonotonic rule systems. First, in order to dedicate further research into nonmonotonic rule systems a new characterization and some new results are given. This characterization and these results lead to new algorithms for computing extensions. Second, a class of nonmonotonic rule systems, called regular nonmonotonic rule systems, is developed. The existence of extensions and semi-monotonicity of regular nonmonotonic rule systems are proved. Third, we prove that each regular nonmonotonic rule system has at most 1.47^n extensions, where n is the number of elements occurring in the system.
31571428
Polynomial time algorithms for computing a representation for minimal unsatisfiable formulas with fixed deficiency
We say a propositional formula F in conjunctive normal form is represented by a formula H and a homomorphism φ, if φ(H) = F. A homomorphism is a mapping consisting of a renaming and an identification of literals. The deficiency of a formula is the difference between the number of clauses and the number of variables. We show that for fixed k ≥ 1 and t ≥ 1 each minimal unsatisfiable formula with deficiency k can be represented by a formula H with deficiency t and a homomorphism and such a representation can be computed in polynomial time.
1096538
Complexity Results for 2CNF Default Theories
This paper is concerned with the complexity of default reasoning with 2CNF default theories (D,W) in which W is a set of literals and D is a set of 2CNF defaults. It is proved that the problem whether a literal occurs in at least one extension can be solved in polynomial time. But the problem whether a literal appears in all extensions is proved to be co-NP-complete. The complexity of some subclasses of 2CNF default theories is also analyzed.
16590593
An approach to hardware/software partitioning for multiple hardware devices model
Computer aided hardware/software partitioning is one of the key challenges in hardware/software co-design. This paper describes a new approach to hardware/software partitioning for multiple hardware-devices model. The partitioning is transformed into a reachability problem of timed automata, and the optimal solution can be obtained by means of an optimal reachability algorithm. To relax the initial condition of partitioning for optimization, two algorithms are designed to explore the dependency relations among processes in the sequential specification. Some experiments are conducted with model checker UPPAAL to show our approach is both effective and efficient.
13480741
Source authentication in group communication systems
Many group communication systems need to enforce a restriction that limits members are authorized to send messages to the group. Receivers therefore need to authenticate message sources before the received messages are accepted. Source authentication in peer-to-peer systems is trivial: the two communication parties can agree on one pair key and use this key to authenticate each other. However, because the group key is shared by all members in a group system, it is quite challenging to identify the sender and determine its authorization. Furthermore, if the authorization can be changed at run-time, source authentication problem can be even harder. This paper presents a source authentication technique called TTA scheme (Transitive Trust Authentication). TTA supports source authentication as well as dynamic authorization change. In addition, its computation and communication overhead is low.
1661187
Siren: catching evasive malware
With the growing popularity of anomaly detection systems, which is due partly to the rise in zero-day attacks, a new class of threats have evolved where the attacker mimics legitimate activity to blend in and avoid detection. We propose a new system called Siren that injects crafted human input alongside legitimate user activity to thwart these mimicry attacks. The crafted input is specially designed to trigger a known sequence of network requests, which Siren compares to the actual traffic. It then flags unexpected messages as malicious. Using this method, we were able to detect ten spyware programs that we tested, many of which attempt to blend in with user activity. This paper presents the design, implementation, and evaluation of the Siren activity injection system, as well as a discussion of its potential limitations
33266884
Flexible Network Support for Mobile Hosts
Fueled by the large number of powerful light-weight portable computers, the expanding availability of wireless networks, and the popularity of the Internet, there is an increasing demand to connect portable computers to the Internet at any time and in any place. However, the dynamic nature of a mobile host's connectivity and its use of multiple network interfaces require more flexible network support than has typically been available for stationary workstations.This paper introduces two flow-oriented mechanisms, in the context of Mobile IP , to ensure a mobile host's robust and efficient communication with other hosts in a changing environment. One mechanism supports multiple packet delivery methods (such as regular IP or Mobile IP) and adaptively selects the most appropriate one to use according to the characteristics of each traffic flow. The other mechanism enables a mobile host to make use of multiple network interfaces simultaneously and to control the selection of the most desirable network interfaces for both outgoing and incoming packets for different traffic flows. We demonstrate the usefulness of these two network layer mechanisms and describe their implementation and performance.
1611793
Type Checking Choreography Description Language
The Web Services Choreography Description Language (WS-CDL) is a W3C specification developed for the description of peer-to-peer collaborations of participants from a global viewpoint. Currently WS-CDL has no rigorous static type checking. We believe that introducing a type system will exclude many design and description errors, and ensure desirable properties of the choreography specifications. In this paper, we took a core language CDL, which covers most of the important features of the WS-CDL, and is more convenient for the study. We developed the abstract syntax and operational semantics of CDL, and defined a collection of rules which can be used to check if choreography is well-typed. Moreover, we also proved some type safety theorems for CDL in the sense that well-typed choreography cannot get stuck. We show how the use of type information can allow us to gain confidence in the correctness of choreography.