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.
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.
13301251
Fixed-parameter tractability of disjunction-free default reasoning
In this paper, the parameter which is the source of the complexity of disjunction-free default reasoning is determined. It is shown that when the value of this parameter is fixed, the disjunction-free default reasoning can be solved in time bounded by a polynomial whose degree does not depend on the parameter. Consequently, disjunction-free default reasoning is fixed parameter tractable.
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.
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.
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.
12214500
Quantifier Rewriting and Equivalence Models for Quantified Horn Formulas
In this paper, quantified Horn formulas with free variables (QHORN*) are investigated. The main result is that any quantified Horn formula Φ of length |Φ| with free variables, |∀| universal quantifiers and an arbitrary number of existential quantifiers can be transformed into an equivalent formula of length O(|∀| ·|Φ|) which contains only existential quantifiers. Moreover, it is shown that quantified Horn formulas with free variables have equivalence models where every existential quantifier is associated with a monotone Boolean function. 
 
The results allow a simple representation of quantified Horn formulas as purely existentially quantified Horn formulas (∃HORN*). An application described in the paper is to solve QHORN*-SAT in O(|∀| ·|Φ|) by using this transformation in combination with a linear-time satisfiability checker for propositional Horn formulas.
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.
2194617
Model Checking Dynamic UML Consistency
UML is widely accepted and extensively used in software modeling. However, using different diagrams to model different aspects of a system brings the risk of inconsistency among diagrams. In this paper, we investigate an approach to check the consistency between the sequence diagrams and statechart diagrams using the SPIN model checker. To deal with the hierarchy structure of statechart diagrams, we propose a formalism called Split Automata, a variant of automata, which is helpful to bridge the statechart diagrams to SPIN efficiently. Compared with the existing work on model checking UML which do not have formal verification for their translation from UML to the model checker, we formally define the semantics and prove that the automatically translated model (i.e. Split Automata) does simulate the UML model. In this way, we can guarantee that the translated model does represent the original model.
15922787
Supporting Mobility in MosquitoNet
The goal of the MosquitoNet project is to provide continuous Internet connectivity to mobile hosts. Mobile hosts must be able to take advantage of the best network connectivity available in any location, whether wired or wireless. We have implemented a mobile IP system that supports seamless switching between different networks and communication devices. In contrast to previous approaches to mobile IP, we believe mobile hosts should not assume any explicit mobility support from the networks they visit, aside from basic Internet connectivity. This decision places extra responsibilities on the mobile hosts themselves. In this paper, we describe the design and implications of such a system. Measurements of our implementation show that the inherent overhead to switch networks (below 10ms) is insignificant compared to the time required to bring up a new communication device.