Search

The class UMU consists of propositional formulas which are a union of minimal unsatisfiable formulas (MU formulas). The structural complexity of UMU formulas depends essentially on the type and degree of intertwining of the MU subformulas. Starting from class of formulas that consist only of clause (or variable) disjoint minimal unsatisfiable subformulas, we study various UMU subclasses given by weakening and these conditions. Generalizing an idea from [6] , we investigate a characterization of UMU formulas by whether they allow transformation into a MU formula by adding literals and/or clauses. It can be shown that simplicity in constructing of such extensions correlates with the degree of intertwining of the MU subformulas. For UMU formulas, however, we can give only extensions that have an exponential size in the worst case. The question of the existence of short MU combinations of MU-formulas by adding literals and clauses remains open. [ABSTRACT FROM AUTHOR]

Conditional independence provides an essential framework to deal with knowledge and uncertainty in Artificial Intelligence, and is fundamental in probability and multivariate statistics. Its associated implication problem is paramount for building Bayesian networks. Unfortunately, the problem does not enjoy an axiomatization, by a finite set of Horn rules, and is already coNP-complete to decide for some fragments of conditional independencies. Saturated conditional independencies form an important fragment whose implication problem is decidable in almost linear time. We establish an axiomatization, by a finite set of Horn rules, for the fragment of generalized saturated conditional independencies. These state the conditional independence between finitely many sets of random variables. The special case of two sets captures Geiger and Pearl's finite axiomatization for saturated conditional independencies. Even for this special case, our completeness proof is new. The proof argument utilizes special probability models where two events have probability one half. Special probability models allow us to establish an equivalence between the implication of generalized saturated conditional independencies and that of formulae in a Boolean propositional fragment. This duality is then extended to a trinity including the implication problem of Delobel's full first-order hierarchical database decompositions. Already for the independence between two sets of random variables, the dualities cannot be extended to cover conditional independencies in general, or first-order hierarchical decompositions. [ABSTRACT FROM AUTHOR]

Abstract: In this paper the correspondence between safe Petri nets and event structures, due to Nielsen, Plotkin and Winskel, is extended to arbitrary nets without self-loops, under the collective token interpretation. To this end we propose a more general form of event structure, matching the expressive power of such nets. These new event structures and nets are connected by relating both notions with configuration structures, which can be regarded as representations of either event structures or nets that capture their behaviour in terms of action occurrences and the causal relationships between them, but abstract from any auxiliary structure. A configuration structure can also be considered logically, as a class of propositional models, or—equivalently—as a propositional theory in disjunctive normal from. Converting this theory to conjunctive normal form is the key idea in the translation of such a structure into a net. For a variety of classes of event structures we characterise the associated classes of configuration structures in terms of their closure properties, as well as in terms of the axiomatisability of the associated propositional theories by formulae of simple prescribed forms, and in terms of structural properties of the associated Petri nets. [Copyright &y& Elsevier]

Abstract: Reasoning from the minimal models of a theory, as fostered by circumscription, is in the area of Artificial Intelligence an important method to formalize common sense reasoning. However, as it appears, minimal models may not always be suitable to capture the intuitive semantics of a knowledge base, aiming intuitively at an exclusive interpretation of disjunctions of atoms, i.e., if possible then assign at most one of the disjuncts the value true in a model. In this paper, we consider an approach which is more lenient and also admits non-minimal models, such that inclusive interpretation of disjunction also may be possible in cases where minimal model reasoning adopts an exclusive interpretation. Nonetheless, in the spirit of minimization, the approach aims at including only positive information that is necessary. This is achieved by closing the set of admissible models of a theory under minimal upper bounds in the set of models of the theory, which we refer to as curbing. We demonstrate this method on some examples, and investigate its semantical and computational properties. We establish that curbing is an expressive reasoning method, since the main reasoning tasks are shown to be PSPACE-complete. On the other hand, we also present cases of lower complexity, and in particular cases in which the complexity is located, just as for ordinary minimal model reasoning, at the second level of the Polynomial Hierarchy, or even below. [Copyright &y& Elsevier]

Abstract: A grid graph has rectangularly arranged vertices with edges permitted only between orthogonally adjacent vertices. The st-connectivity principle states that it is not possible to have a red path of edges and a green path of edges which connect diagonally opposite corners of the grid graph unless the paths cross somewhere. We prove that the propositional tautologies which encode the st-connectivity principle have polynomial-size Frege proofs and polynomial-size -Frege proofs. For bounded-width grid graphs, the st-connectivity tautologies have polynomial-size resolution proofs. A key part of the proof is to show that the group with two generators, both of order two, has word problem in alternating logtime (Alogtime) and even in . Conversely, we show that constant depth Frege proofs of the st-connectivity tautologies require near-exponential size. The proof uses a reduction from the pigeonhole principle, via tautologies that express a “directed single source” principle SINK, which is related to Papadimitriou''s search classes PPAD and PPADS (or, PSK). The st-connectivity principle is related to Urquhart''s propositional Hex tautologies, and we establish the same upper and lower bounds on proof complexity for the Hex tautologies. In addition, the Hex tautology is shown to be equivalent to the SINK tautologies and to the one-to-one onto pigeonhole principle. [Copyright &y& Elsevier]