检索结果-内蒙古大学图书馆

Default reasoning from conditional knowledge bases: Complexity and tractable cases

ARTIFICIAL INTELLIGENCE 2000年第2期124卷 169-241页

作者： Eiter, T Lukasiewicz, T Vienna Univ Technol Inst & Ludwig Wittgenstein Labor Informat Syst A-1040 Vienna Austria

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi --> psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default phi --> psi, does KB entail phi --> psi? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： reasoning under uncertainty conditional knowledge bases default reasoning nonmonotonic inference computational complexity polynomial-time algorithms Horn knowledge bases and variants

来源：评论

学校读者我要写书评

暂无评论

Reconfiguration models and algorithms for stateful interactive processes

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1999年第3期25卷 401-415页

作者： Varvarigou, TA Anagnostou, ME Ahuja, SR Natl Tech Univ Athens Dept Elect Engn & Comp Sci GR-15773 Athens Greece AT&T Bell Labs Lucent Technol Murray Hill NJ 07974 USA

In this paper, we present new results in the area of reconfiguration of stateful interactive processes in the presence of faults. More precisely, we consider a set of servers/processes that have the same functionality, i.e., are able to perform the same tasks and provide the same set of services to their clients. In the case when several of them turn out to be faulty, we want to reconfigure the system so that the clients of the faulty servers/processes are served by some other, fault-free, servers of the system in a way that is transparent to all the system clients. We propose a new method for reconfiguring in the presence of faults: compensation paths. Compensation paths are an efficient way of shifting spare resources from where they are available to where they are needed. We also present optimal and suboptimal simple reconfiguration algorithms of low polynomial time complexity O(nmlog(n(2)/m)) for the optimal and O(m) for the suboptimal algorithms, where M is the number of processes and m is the number of primary-backup relationships. The optimal algorithms compute the way to reconfigure the system whenever the reconfiguration is possible. The suboptimal algorithms may sometimes fail to reconfigure the system, although reconfiguration would be possible by using the optimal centralized algorithms. However, suboptimal algorithms have other competitive advantages over the centralized optimal algorithms with regard to time complexity and communication overhead.

关键词： reconfiguration of stateful processes compensation paths polynomial-time algorithms optimal centralized algorithms suboptimal distributed and hybrid algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding an even simple path in a directed planar graph

引用

SIAM JOURNAL ON COMPUTING 1999年第2期29卷 685-695页

作者： Nedev, ZP Univ Cape Town Dept Comp Sci ZA-7700 Rondebosch South Africa

In this paper we show that the following problem, the even simple path (ESP) problem for directed planar graphs, is solvable in polynomial time: Given: a directed planar graph G = (V, E) and two nodes s (startingnode);t (targetnode) is an element of V;Find: a simple path (i.e., without repeated nodes) from s to t of even length. (The length of the path is the number of edges it contains.).

关键词： labeled directed graphs NP-completeness polynomial-time algorithms regular expressions simple paths planar graphs

来源：评论

学校读者我要写书评

暂无评论

Optimal WDM schedules for optical star networks

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 1999年第3期7卷 446-456页

作者： Dasylva, A Srikant, R Nokia Res Ctr Burlington MA 01803 USA Univ Illinois Dept Gen Engn Urbana IL 61801 USA Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA

We consider single-hop wavelength-division multiplexed networks in which the transmitters take a nonzero amount of time, called tuning latency, to tune from one wavelength to another. For such networks, we show that, under certain conditions on the traffic matrix, there exist polynomial-time algorithms that produce the optimal schedule. Further, the tuning latency is masked in the length of the optimal schedule. Using Chernoff-Hoeffding bounds, we show that the condition on the traffic matrix is satisfied with high probability when the wavelength reuse factor is large, i.e., the number of nodes is large compared to the number of wavelengths. Simulation results show the dramatic improvement in the performance of the network using our algorithm as compared with other heuristics.

关键词： optical networks polynomial-time algorithms scheduling wavelength-division multiplexing

来源：评论

学校读者我要写书评

暂无评论

A three-dimensional matching model for perishable production scheduling

引用

DISCRETE APPLIED MATHEMATICS 1999年第1期92卷 1-15页

作者： Arbib, C Pacciarelli, D Smriglio, S Univ Rome Dipartimento Automat & Informat I-00146 Rome Italy Univ Aquila Dipartimento Matemat Pura & Applicata I-67010 Coppito Italy Univ Roma Tor Vergata Ctr Vito Volterra I-00133 Rome Italy

In the production of perishable goods, particular stress is often given to performance indicators generally less critical in such manufacturing settings as metal-cutting, or mechanical/electronic assembly, For instance, in food or biochemical productions, a prominent interest of the producer is to reduce the time from distribution to the so-called best-before end. A scheduling problem with a goal of this sort is here addressed. The decision variables considered are launching and completion times of parts in a production line with critical aspects in the initial and/or final stages. The basic problem is to find an assignment of a maximum number of products to launching and completion times, so that no two products are assigned the same launching or completion time: feasible solutions have therefore the form of three-dimensional matchings. The problem is studied under two independent respects, assuming either (i) the relative perishability of products or (ii) the feasibility of launching/completion time pairs not affected by the intermediate transformation stage. We show that the problem is NP-Complete, even under such a ranking assumption as (i), whereas is in P under assumption (ii). polynomial-time algorithms are also proposed to solve other optimization versions of the problem (in two cases, based on the identification of a matroid structure). (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： scheduling three-dimensional matching polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

When difference in machine loads leads to efficient scheduling in open shops

引用

ANNALS OF OPERATIONS RESEARCH 1999年第0期92卷 211-239页

作者： Kononov, A Sevastianov, S Tchernykh, I Russian Acad Sci Inst Math Siberian Branch Novosibirsk 630090 90 Russia Novosibirsk State Tech Univ Dept Algebra Novosibirsk 630092 92 Russia

We consider the open shop problem with n jobs, m machines, and the minimum makespan criterion. Let l(i) stand for the load of the ith machine, l(max) be the maximum machine load, and p(max) be the maximum operation length. Suppose that the machines are numbered in nonincreasing order of their loads and that p(max) = 1, while other processing times are numbers in the interval [0, 1]. Then, given an instance of the open shop problem, we define its vector of differences VOD = (Delta(1),...,Delta(m)), where Delta(i) = l(max) - l(i). An instance is called normal if its optimal schedule has length l(max). A vector Delta is an element of R-m is called normalizing if every instance with VOD = Delta is normal. A vector Delta is an element of R-m is called efficiently normalizing if it is normalizing and there is a polynomial-time algorithm which for any instance with VOD = Delta constructs its optimal schedule. In this paper, a few nontrivial classes of efficiently normalizing vectors are found in R-m . It is also shown that the vector (0, 0, 2) is the unique minimal normalizing vector in R-3, and that there are at least two minimal normalizing vectors in R-4 .

关键词： open shops polynomial-time algorithms machine load scheduling

来源：评论

学校读者我要写书评

暂无评论

A convergence analysis of the scaling-invariant primal-dual path-following algorithms for second-order cone programming

引用

OPTIMIZATION METHODS & SOFTWARE 1999年第1-4期11-2卷 141-182页

作者： Tsuchiya, T Inst Stat Math Minato Ku Tokyo 1068569 Japan

In this paper we study primal-dual path-following algorithms for second-order cone programming problems (SOCP). We extend the standard long-step/semilong-step/short-step primal-dual path-following alogorithms for LP and SDP to SOCP, and prove that the long-step algorithm using the NT direction and the HRVW/KSH/M direction have O(n log epsilon(-1)) iteration-complexity and O(n(3/2) log epsilon(-1)) iteration-complexity, respectively, to reduce the duality gap by a factor of 1/epsilon, where n is the number of the second-order cones. We also show that the short and semilong-step algorithms using the NT direction and the HRVW/KSH/M direction have O(root n log epsilon(-1)) and O(n log epsilon(-1)) iteration-complexities, respectively.

关键词： second-order cone programming interior-point methods polynomial-time algorithms primal-dual path-following methods Euclidean Jordan algebra homogeneous and self-dual cone programming

来源：评论

学校读者我要写书评

暂无评论

The inverse satisfiability problem

引用

SIAM JOURNAL ON COMPUTING 1998年第1期28卷 152-163页

作者： Kavvadias, D Sideri, M Univ Patras Dept Math GR-26110 Patras Greece Athens Univ Econ & Business Dept Comp Sci Athens Greece

We study the complexity of telling whether a set of bit-vectors represents the set of all satisfying truth assignments of a Boolean expression of a certain type. We show that the problem is coNP-complete when the expression is required to be in conjunctive normal form with three literals per clause (3CNF). We also prove a dichotomy theorem analogous to the classical one by Schaefer, stating that, unless P=NP, the problem can be solved in polynomial time if and only if the clauses allowed are all Horn, or all anti-Horn, or all 2CNF, or all equivalent to equations modulo two.

关键词： computational complexity polynomial-time algorithms coNP-completeness Boolean satisfiability model

来源：评论

学校读者我要写书评

暂无评论

Scheduling in and out forests in the presence of communication delays

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1996年第10期7卷 1065-1074页

作者： Varvarigou, TA Roychowdhury, VP Kailath, T Lawler, E UNIV CALIF LOS ANGELES DEPT ELECT ENGNLOS ANGELESCA 90095 STANFORD UNIV DEPT ELECT ENGNSTANFORDCA 94305 UNIV CALIF BERKELEY DEPT ELECT ENGN & COMP SCIBERKELEYCA

We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays, Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete [16], [10]. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem [12], [14], [10]. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961 [12];however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m - 2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum.

关键词： communication delays out-forest precedence graphs multiprocessor architectures out-forest precedence graphs optimal deterministic schedules polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Finding minimal siphons in general Petri nets

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1996年第11期E79A卷 1817-1824页

作者： Tanimoto, S Yamauchi, M Watanabe, T Department of Circuits and Systems Faculty of Engineering Hiroshima University Higashi-Hiroshima-shi 739 Japan

A siphon (or alternatively a structural deadlock) of a Petri net is defined as a set S of places such that existence of any edge from a transition t to a place of S implies that there is an edge from some place of S to t. A minimal siphon is a siphon such that any proper subset is not a siphon. The results of the paper are as follows. (1) The problem of deciding whether or not a given Petri net has a minimum siphon (i.e., a minimum-cardinality minimal siphon) is NP-complete. (2) A polynomial-time algorithm to find, if any, a minimal siphon or even a maximal class of mutually disjoint minimal siphons of a general Petri net is proposed.

关键词： general Petri nets minimal siphons polynomial-time algorithms strongly connectedness NP-completeness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：