8778857
On Models for Quantified Boolean Formulas
A quantified Boolean formula is true, if for any existentially quantified variable there exists a Boolean function depending on the preceding universal variables, such that substituting the existential variables by the Boolean functions results in a true formula. We call a satisfying set of Boolean functions a model. In this paper, we investigate for various classes of quantified Boolean formulas and various classes of Boolean functions the problem whether a model exists. Furthermore, for these classes the complexity of the model checking problem – whether a set of Boolean functions is a model for a formula – will be shown. Finally, for classes of Boolean functions we establish some characterizations in terms of quantified Boolean formulas which have such a model. For example, roughly speaking any satisfiable quantified Boolean Horn formula can be satisfied by monomials and vice versa.
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.
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.
7900372
Complexity of the Unique Extension Problem in Default Logic
In this paper we analyze the problem of checking whether a default theory has a single extension. This problem is important for at least three reasons. First, if a theory has a single extension, nonmonotonic inference can be reduced to entailment in propositional logic (which is computationally easier) using the set of consequences of the generating defaults. Second, a theory with many extensions is typically weak i.e., it has few consequences; this indicates that the theory is of little use, and that new information has to be added to it, either as new formulae, or as preferences over defaults. Third, some applications require as few extensions as possible (e.g. diagnosis). We study the complexity of checking whether a default theory has a single extension. We consider the combination of several restrictions of default logics: seminormal, normal, disjunction-free, unary, ordered. Complexity varies from the first to the third level of the polynomial hierarchy. The problem of checking whether a theory has a given number of extensions is also discussed.
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.
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.
15041582
Towards the Semantics and Verification of BPEL4WS
In this paper, we discuss the semantics of BPEL4WS language which is a de facto standard for specifying and execution workflow specification for web service composition and orchestration. We propose a language @m-BPEL that includes most primitive and structured activities of BPEL4WS, and define its semantics. As the Timed Automata (TA) is powerful in designing real-time models with multiple clocks and has well developed automatic tool support, we define a map from @m-BPEL into composable TA. Therefore, the properties we want to check can be verified in TA network correspondingly. Furthermore, we prove that the mapping from @m-BPEL to TA is a simulation, which means that the TA network simulates correctly the corresponding @m-BPEL specification. The case study with model checker Uppaal shows that our method is effective, and a Java supporting tool based on Uppaal model checker engine has been developed.
8975753
Scanning microarrays at multiple intensities enhances discovery of differentially expressed genes
MOTIVATION
Scanning parameters are often overlooked when optimizing microarray experiments. A scanning approach that extends the dynamic data range by acquiring multiple scans of different intensities has been developed.


RESULTS
Data from each of three scan intensities (low, medium, high) were analyzed separately using multiple scan and linear regression approaches to identify and compare the sets of genes that exhibit statistically significant differential expression. In the multiple scan approach only one-third of the differentially expressed genes were shared among the three intensities, and each scan intensity identified unique sets of differentially expressed genes. The set of differentially expressed genes from any one scan amounted to < 70% of the total number of genes identified in at least one scan. The average signal intensity of genes that exhibited statistically significant changes in expression was highest for the low-intensity scan and lowest for the high-intensity scan, suggesting that low-intensity scans may be best for detecting expression differences in high-signal genes, while high-intensity scans may be best for detecting expression differences in low-signal genes. Comparison of the differentially expressed genes identified in the multiple scan and linear regression approaches revealed that the multiple scan approach effectively identifies a subset of statistically significant genes that linear regression approach is unable to identify. Quantitative RT-PCR (qRT-PCR) tests demonstrated that statistically significant differences identified at all three scan intensities can be verified.


AVAILABILITY
The data presented can be viewed at http://www.ncbi.nlm.nih.gov/geo/ under GEO accession no. GSE3017.
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.
1211132
A Multi-Agent System for E-Business Processes Monitoring in a Web-Based Environment
In this paper, we present a multi-agent system MAGS for the e-business processes monitoring in a web-based environment. We classify the types of agents in MAGS by their monitoring capabilities. An algorithm is given to explain the mechanism of supervising and controlling the execution of business processes. An abstract model of alerts, which can give warnings of infringement on business policies, is proposed. Access control can also be realized by MAGS, which manifests in delivering different view of the business process to different roles participate in it. Being successfully adopted in a customer service management system, MAGS has been proven flexible and practical.
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.