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
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.
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.
43741261
Parallel Product of Event Structures
Event structures were introduced by Nielsen, Plotkin and Winskel [5] as a model for computational processes. These were essentially sets of events with relations expressing causal dependence and conflicts between them. These structures, also called prime event structures, were shown to be connected both with a class of acyclic Petri nets (called by the authors occurrence nets) and with a class of domains (finitary prime algebraic coherent domains). Though a very pleasant model of computation, prime event structures can lead to tedious definitions for more sophisticated constructions such as parallel product or exponentiation. In subsequent papers [8,9], Winskel introduced a more general class of event structures called stable event structures, for which such constructions are defined categorically. Although stable event structures themselves are slightly more complicated than prime event structures, constructions on them can be defined in an elegant way. In general, category theory has proven very useful for computer science. When constructions are formulated in categorical terms, not only can the required universal properties provide some guideline in the definitions, the associated morphisms may contain suggestions of computational interest as well. Moving to more general structures, however, can sometimes shield the intuitions about the model. In the case of stable event structures, the causality relation on events is not explicitly given, but is derived from an enabling relation on events. This makes such event structures a little hard to visualize, and one may wonder whether a more manageable notion could be devised. Moreover, unlike prime event structures, it is not clear if stable event structures correspond to a class of Petri nets, in the sense of [5]. Flow event structures were proposed in [2] as an intermediate between prime event structures and stable event structures, suitable both for graphical representation and for an easy definition of process operators. Among these operators the critical one is the
205118584
dI-Domains as Prime Information Systems
Abstract This paper introduces prime information systems. Prime information systems determine dI-domains and stable approximable mappings give stable functions, and vice versa. The notion of rigid embedding is captured by a subsystem relation. Under this relation, prime information systems form a complete partial order (cpo). Constructions like lifting, sum, product, and function space are proposed which induce continuous functions on the cpo. In this way recursive prime information systems can be defined using fixed point theory.
1726106
Defaults in Domain Theory
Abstract This paper uses ideas from artificial intelligence to show how default notions can be defined over Scott domains. We combine these ideas with ideas arising in domain theory to shed some light on the properties of nonmonotonicity in a general model-theoretic setting. We consider in particular a notion of default nonmonotonic entailment between prime open sets in the Scott topology of a domain. We investigate in what ways this notion obeys the so-called laws of cautious monotony and cautious cut , proposed by Gabbay, Kraus, Lehmann, and Magidor. Our notion of nonmonotonic entailment does not necessarily satisfy cautious monotony, but does satisfy cautious cut. In fact, we show that any reasonable notion of nonmonotonic entailment on prime opens over a Scott domain, satisfying in particular the law of cautious cut, can be concretely represented using our notion of default entailment. We also give a variety of sufficient conditions for defaults to induce cumulative entailments, those satisfying cautious monotony. In particular, we show that defaults with unique extensions are a representation of cumulative nonmonotonic entailment. Furthermore, a simple characterization is given for those default sets which determine unique extensions in coherent domains. Finally, a characterization is given for Scott domains in which default entailment must be cumulative. This is the class of daisy domains ; it is shown to be cartesian closed, a purely domain-theoretic result.
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.
41994930
On the partition and coloring of a graph by cliques
Abstract We first introduce the concept of the k -chromatic index of a graph, and then discuss some of its properties. A characterization of the clique partition number of the graph G ⋁ K c m for any simple graph G is given, together with some of its applications. Graphs with maximum valency 3 are also considered.
38503566
Pseudo-one-factorizations of regular graphs of odd order - II. products of graphs
Abstract We study the pseudo-one-factorization of regular graphs of odd order. It is shown that some classes of products (including composition and cartesian product) of graphs are pseudo-one- factorizable. In particular, we prove that a complete regular t -partite graph of odd order has this property.
30701744
Single change covering designs
A single-change covering designSC (v, k, b) on av-setV is a sequence ofb k-sets (blocks) onV which together cover every pair of elements ofV at least once, such that two successive blocks havek−1 elements in common. It is desirable to minimizeb. Some constructions and lower bounds forb are given.
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.