15122247
Some Monoidal Closed Categories of Stable Domains and Event Structures
This paper introduces the following new constructions on stable domains and event structures: the tensor product; the linear function space; and the exponential. These give rise to a monoidal closed category of dI-domains and to stable event structures, which can be used to interpret intuitionistic linear logic. Finally, the usefulness of the category of stable event structures for modeling concurrency and its relation to other models are discussed.
10438151
Complexity of power default reasoning
This paper derives a new and surprisingly low complexity result for inference in a new form of Reiter's propositional default logic (1980). The problem studied here is the default inference problem whose fundamental importance was pointed out by Kraus, Lehmann, and Magidor (1980). We prove that "normal" default inference, in propositional logic, is a problem complete for co-NP(3), the third level of the Boolean hierarchy. Our result (by changing the underlying semantics) contrasts favorably with a similar result of Gottlob (1992), who proves that standard default inference is II/sub 2//sup P/-complete. Our inference relation also obeys all of the laws for preferential consequence relations set forth by Kraus, Lehmann, and Magidor (1990). In particular we get the property of being able to reason by cases and the law of cautious monotony. Both of these laws fail for standard propositional default logic. The key technique for our results is the use of Scott's domain theory to integrate defaults into partial model theory of the logic, instead of keeping defaults as quasiproof rules in the syntax. In particular, reasoning disjunctively entails using the Smyth powerdomain.
717123
Experimenting with Power Default Reasoning
In this paper we explore the computational aspects of Propositional Power Default Reasoning (PDR), a form of non-monotonic reasoning in which the underlying logic is Kleene's 3-valued propositional logic. PDR leads to a concise meaning of the problem of skeptical entailment which has better complexity characteristics than the usual formalisms (co-NP(3)-Complete instead of ?2P-Complete). We take advantage of this in an implementation called powdef to encode and solve hard graph problems and explore randomly generated instances of skeptical entailment.
14387948
Axiomatic Aspects of Default Inference
This paper studies axioms for nonmonotonic consequences from a semantics-based point of view, focusing on a class of mathematical structures for reasoning about partial information without a predefined syntax/logic. This structure is called a default structure. We study axioms for the nonmonotonic consequence relation derived from extensions as in Reiter's default logic, using skeptical reasoning, but extensions are now used for the construction of possible worlds in a default information structure. 
In previous work we showed that skeptical reasoning arising from default-extensions obeys a well-behaved set of axioms including the axiom of cautious cut. We show here that, remarkably, the converse is also true: any consequence relation obeying this set of axioms can be represented as one constructed from skeptical reasoning. We provide representation theorems to relate axioms for nonmonotonic consequence relation and properties about extensions, and provide one-to-one correspondence between nonmonotonic systems which satisfies the law of cautious monotony and default structures with unique extensions. Our results give a theoretical justification for a set of basic rules governing the update of nonmonotonic knowledge bases, demonstrating the derivation of them from the more concrete and primitive construction of extensions. It is also striking to note that proofs of the representation theorems show that only shallow extensions are necessary, in the sense that the number of iterations needed to achieve an extension is at most three. All of these developments are made possible by taking a more liberal view of consistency: consistency is a user defined predicate, satisfying some basic properties.
14595938
Clausal Logic and Logic Programming in Algebraic Domains
We introduce a domain-theoretic foundation for disjunctive logic programming. This foundation is built on clausal logic, a representation of the Smyth powerdomain of any coherent algebraic dcpo. We establish the completeness of a resolution rule for inference in such a clausal logic; we introduce a natural declarative semantics and a fixed-point semantics for disjunctive logic programs, and prove their equivalence; finally, we apply our results to give both a syntax and semantics for default logic in any coherent algebraic dcpo. 2001 Elsevier Science
12232435
Rational Transformations of Formal Power Series
Formal power series are an extension of formal languages. Recognizable formal power series can be captured by the so-called weighted finite automata, generalizing finite state machines. In this paper, motivated by codings of formal languages, we introduce and investigate two types of transformations for formal power series. We characterize when these transformations preserve rationality, generalizing the recent results of Zhang [15] to the formal power series setting. We show, for example, that the "square-root" operation, while preserving regularity for formal languages, preserves rationality for formal power series when the underlying semiring is commutative or locally finite, but not in general.
42909091
Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem
Path relinking is a method to generate new solution by exploring trajectories that connect high quality solutions. In this paper, a class of new hybrid heuristics are proposed by combining a genetic algorithm and path relinking and applying these to a multiple-level warehouse layout problem. Parallel and series combinations to integrate crossover and mutation operations of a genetic algorithm with path relinking are investigated. We proposed position and sequence based path relinking methods to connect two solutions, which are either elites or ones selected randomly. Extensive experiments are carried out to compare the performance of the new heuristics.
7914535
Stereoscopic Video Synthesis from a Monocular Video
This paper presents an automatic and robust approach to synthesize stereoscopic videos from ordinary monocular videos acquired by commodity video cameras. Instead of recovering the depth map, the proposed method synthesizes the binocular parallax in stereoscopic video directly from the motion parallax in monocular video, The synthesis is formulated as an optimization problem via introducing a cost function of the stereoscopic effects, the similarity, and the smoothness constraints. The optimization selects the most suitable frames in the input video for generating the stereoscopic video frames. With the optimized selection, convincing and smooth stereoscopic video can be synthesized even by simple constant-depth warping. No user interaction is required. We demonstrate the visually plausible results obtained given the input clips acquired by ordinary handheld video camera.
13849872
As-consistent-As-possible compositing of virtual objects and video sequences
We present an efficient approach that merges the virtual objects into video sequences taken by a freely moving camera in a realistic manner. The composition is visually and geometrically consistent through three main steps. First, a robust camera tracking algorithm based on key frames is proposed, which precisely recovers the focal length with a novel multi-frame strategy. Next, the concerned 3D models of the real scenes are reconstructed by means of an extended multi-baseline algorithm. Finally, the virtual objects in the form of 3D models are integrated into the real scenes, with special cares on the interaction consistency including shadow casting, occlusions, and object animation. A variety of experiments have been implemented, which demonstrate the robustness and efficiency of our approach. Copyright © 2006 John Wiley & Sons, Ltd.
36095353
Extremal Regular Graphs with Prescribed Odd Girth
The odd girth of a graph G gives the length of a shortest odd cycle in G. Let ?(k, g) denote the smallest n such that there exists a k-regular graph of order n and odd girth g. It is known that ?(k, g) ? kg/2 and that ?(k, g) = kg/2 if k is even. The exact values of ?(k, g) are also known if k = 3 or g = 5. Let ?x?e denote the smallest even integer no less than x, ?(g) = (?1)g ? 1/2, and s(k) = min {p + q | k = pq, where p and q are both positive integers}. It is proved that if k ? 5 and g ? 7 are both odd, then formula] with the exception that ?(5, 7) = 20.
37771428
Some New Bounds on Single-Change Covering Designs
A single-change covering design SCD(v, k, b) on a c-set V is a sequence of b k-sets (blocks) on V that together cover every pair of elements of V at least once, such that two successive blocks have k-1 elements in common. Let f(v,k) denote the smallest b for which there exists an SCD(v, k, b). Some new upper and lower bounds for f(v,k) are given.