作者：
Eiter, TIbaraki, TMakino, KVienna Univ Technol
Inst Ludwig Wittgenstein Labor Informat Syst Knowledge Based Syst Grp A-1040 Vienna Austria Kyoto Univ
Grad Sch Informat Dept Appl Math & Phys Kyoto 606 Japan Osaka Univ
Grad Sch Engn Sci Dept Syst & Human Sci Toyonaka Osaka 560 Japan
Model-based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper,...
详细信息
Model-based reasoning has been proposed as an alternative form of representing and accessing logical knowledge bases. In this approach, a knowledge base is represented by a set of characteristic models. In this paper, we consider computational issues when combining logical knowledge bases, which are represented by their characteristic models;in particular, we study taking their logical intersection. We present low-order polynomial time algorithms or prove intractability for the major computation problems in the context of knowledge bases which are Horn theories. In particular, we show that a model of the intersection Sigma of Horn theories Sigma(1),...,Sigma(l) represented by their characteristic models, can be found in linear time, and that some characteristic model of Sigma can be found in polynomial time. Moreover, we present an algorithm which enumerates all the models of Sigma with polynomial delay. The analogous problem for the characteristic models is proved to be intractable, even if the possible exponential size of the output is taken into account. Furthermore, we show that approximate computation of the set of characteristic models is difficult as well. Nonetheless, we show that deduction from Sigma is possible for a large class of queries in polynomial time, while abduction turns out to be intractable. We also consider a generalization of Horn theories, and prove negative results for the basic questions, indicating that an extension of the positive results beyond Horn theories is not immediate. (C) 1999 Elsevier Science B.V. All rights reserved.
Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses) has been recognized as an important principle of common-sense reasoning. Since logical knowledge representation is commonl...
详细信息
Abductive reasoning (roughly speaking, find an explanation for observations out of hypotheses) has been recognized as an important principle of common-sense reasoning. Since logical knowledge representation is commonly based on nonclassical formalisms like default logic, autoepistemic logic, or circumscription, it is necessary to perform abductive reasoning from theories (i.e., knowledge bases) of nonclassical logics. In this paper, we investigate how abduction can be performed from theories in default logic. In particular, we present a basic model of abduction from default theories. Different modes of abduction are plausible, based on credulous and skeptical default reasoning;they appear useful for different applications such as diagnosis and planning, Moreover, we thoroughly analyze the complexity of the main abductive reasoning tasks, namely finding an explanation, deciding relevance of a hypothesis, and deciding necessity of a hypothesis. These problems are intractable even in the propositional case, and we locate them into the appropriate slots of the polynomial hierarchy. However, we also present known classes of default theories for which abduction is tractable. Moreover, we also consider first-order default theories, based on domain closure and the unique names assumption, In this setting, the abduction tasks are decidable, but have exponentially higher complexity than in the propositional case. (C) 1997 Elsevier Science B.V.
When a query fails, it is more cooperative to identify the cause of failure, rather than just to report the empty answer set. When there is not a cause per se for the query's failure, it is then worthwhile to repo...
详细信息
When a query fails, it is more cooperative to identify the cause of failure, rather than just to report the empty answer set. When there is not a cause per se for the query's failure, it is then worthwhile to report the part of the query which failed. To identify a Minimal Failing Subquery (MFS) of the query is the best way to do this. (This MFS is not unique;there may be many of them.) Likewise, to identify a Maximal Succeeding Subquery (XSS) can help a user to recast a new query that leads to a non-empty answer set. Database systems do not provide the functionality of these types of cooperative responses. This may be, in part, because algorithmic approaches to finding the MFSs and the XSSs to a failing query are not obvious. The search space of subqueries is large. Despite work on MFSs in the past, the algorithmic complexity of these identification problems had remained uncharted. This paper shows the complexity profile of MFS and XSS identification. It is shown that there exists a simple algorithm for finding an MFS or an XSS by asking N subsequent queries, in which N is the length of the query. To find more MFSs (or XSSs) can be hard. It is shown that to find N MFSs (or XSSs) is NP-hard. To find k MFSs (or XSSs), for a fixed k, remains polynomial. An optimal algorithm for enumerating MFSs and XSSs, ISHMAEL, is developed and presented. The algorithm has ideal performance in enumeration, finding the first answers quickly, and only decaying toward intractability in a predictable manner as further answers are found. The complexity results and the algorithmic approaches given in this paper should allow for the construction of cooperative facilities which identify MFSs and XSSs for database systems. These results are relevant to a number of problems outside of databases tao, and may find further application.
Pattern matching is an important operation used in many applications such as functional programming, rewriting, and rule-based expert systems. By preprocessing the patterns into a deterministic finite state automaton,...
详细信息
Pattern matching is an important operation used in many applications such as functional programming, rewriting, and rule-based expert systems. By preprocessing the patterns into a deterministic finite state automaton, we can rapidly select the matching pattern(s) in a single scan of the relevant portions of the input term. This automaton is typically based on left-to-right traversal of the patterns. By adapting the traversal order to suit the set of input patterns, it is possible to considerably reduce the space and matching time requirements of the automaton. The design of such adaptive automata is the focus of this paper. We first formalize the notion of an adaptive traversal. We then present several strategies for synthesizing adaptive traversal orders aimed at reducing space and matching time complexity. In the worst case, however, the space requirements can be exponential in the size of the patterns. We show this by establishing an exponential lower bound on space that is independent of the traversal order used. We then discuss an orthogonal approach to space minimization based on direct construction of optimal directed acyclic graph (dag) automata. Finally, our work stresses the impact of typing in pattern matching. In particular, we show that several important problems (e.g., lazy pattern matching in ML) are computationally difficult in the presence of type disciplines, whereas they can be served efficiently in the untyped setting.
For a system consisting of a set of sensors S = {S1, S2, ..., S(m)} and a set of objects O = {O1, O2, ..., O(n)}, there are information constraints given by a relation R subset-or-equal-to S x O such that (S(i), O(j))...
详细信息
For a system consisting of a set of sensors S = {S1, S2, ..., S(m)} and a set of objects O = {O1, O2, ..., O(n)}, there are information constraints given by a relation R subset-or-equal-to S x O such that (S(i), O(j)) is-an-element-of R if and only if S(i) is capable of detecting O(j). Each (S(i), O(j)) is-an-element-of R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H subset-of-equal-to O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1;(b) uniform formulation where (S(i), O(j)) is-an-element-of R, for all S(i) is-an-element-of S, O(j) is-an-element-of O;(c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection;(b) probabilistically independent detection;(c) decomposable systems under additive and nonfractional multiplicative measures;and (d) matroid systems.
作者：
RAO, NSVOak Ridge Nat. Lab.
TN USA Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions
Systems that can be modeled as graphs, such thal nodes represent the components and the edges represent the fault propagation between the components, are considered. Some components are equipped with alarms that ring ...
详细信息
Systems that can be modeled as graphs, such thal nodes represent the components and the edges represent the fault propagation between the components, are considered. Some components are equipped with alarms that ring in response to faulty conditions. In these systems, two types of problems are studied: a) fault diagnosis, and b) alarm placement. The fault diagnosis problems deal with computing the set of all potential failure sources that correspond to a set of ringing alarms A(R). First, the single faults, where exactly one component can become faulty at any time, are considered. Systems are classified into zero-time and nonzero-time systems based on fault propagation times, and the latter is further classified based on the knowledge of propagation times. For each of these classes algorithms are presented for single fault diagnosis. The problem of detecting multiple faults is shown to be NP-complete. An alarm placement problem, that requires a single fault to be uniquely diagnosed, is examined;various versions of this problem are shown to be NP-complete. The single fault diagnosis algorithms have been implemented and tested.
作者：
RAO, NSVDept. of Comput. Sci.
Old Dominion Univ. Norfolk VA USA Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions
The problem of diagnosing single faults is addressed for systems whose fault propagation properties can be modeled as directed graphs. In these systems, the nodes represent components and the edges represent fault pro...
详细信息
The problem of diagnosing single faults is addressed for systems whose fault propagation properties can be modeled as directed graphs. In these systems, the nodes represent components and the edges represent fault propagation between the components. Some of the components are equipped with alarms that become active in response to faulty conditions. Two algorithms FORWARD and BACKWARD for computing the set of all potential candidates for a single fault that corresponds to a given set of active alarms, are studied. The algorithm FORWARD moves forward from candidate nodes checking to see if they satisfy the alarm condition, and the algorithm BACKWARD moves backwards from the alarms. In terms of worst-case time complexity the algorithm BACKWARD is better. These two algorithms are analyzed using systems that are uniformly and randomly generated. In terms of the expected number of distinct nodes that are visited, the algorithm FORWARD is shown to be better, and in terms of the total number of node visits the algorithm BACKWARD is found to be better. Thus these algorithms are suited for different modes of storing the system graph.
We present a THETA(n log n) time algorithm to check similarity, under isogonal affine transformation (i.e. translation, rotation and scaling), of two given sets of n points in plane. We obtain an O(n log n) time algor...
详细信息
We present a THETA(n log n) time algorithm to check similarity, under isogonal affine transformation (i.e. translation, rotation and scaling), of two given sets of n points in plane. We obtain an O(n log n) time algorithm and establish-OMEGA(n log n) lower bound for this problem under the linear search tree model. Our analysis implies that the main source of complexity for this problem arises from the "combinatorial" nature rather than the "affiness" of the problem.
暂无评论