Sequent calculi for propositional star-free likelihood logic

We consider classical, multisuccedent intuitionistic, and intuitionistic sequent calculi for propositional likelihood logic. We prove the admissibility of structural rules and cut rule, invertibility of rules, correctness of the calculi, and completeness of the classical calculus with respect to given semantics.__________Published in Lietuvos Matematikos Rinkinys, Vol. 45, No. 1, pp. 3–21, January–March, 2005.     

Proof complexity of propositional default logic

Default logic is one of the most popular and successful formalisms for non-monotonic reasoning. In 2002, Bonatti and Olivetti introduced several sequent calculi for credulous and skeptical reasoning in propositional default logic. In this paper we examine these calculi from a proof-complexity perspective. In particular, we show that the calculus for credulous reasoning obeys almost the same bounds on the proof size as Gentzen??s system LK. Hence proving lower bounds for credulous reasoning will be as hard as proving lower bounds for LK. On the other hand, we show an exponential lower bound to the proof size in Bonatti and Olivetti??s enhanced calculus for skeptical default reasoning.     

A note on propositional proof complexity of some Ramsey-type statements

A Ramsey statement denoted ${n \longrightarrow (k)^2_2}$ says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(n ^k ) and with terms of size ${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$ . Let r _k be the minimal n for which the statement holds. We prove that RAM(r _k , k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák??s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4 ^k , k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R.     

The complexity of numerical methods for elliptic partial differential equations

We consider three Ritz-Galerkin procedures with Hermite bicubic, bicubic spline and linear triangular elements for approximating the solution of self-adjoint elliptic partial differential equations and a collocation with Hermite bicubics method for general linear elliptic equations defined on general two dimensional domains with mixed boundary conditions. We systematically evaluate these methods by applying them to a sample set of problems while measuring various performance criteria. The test data suggest that collocation is the most efficient method for general use.     

The complexity of completing partial Latin squares

Completing partial Latin squares is shown to be NP-complete. Classical embedding techniques of Hall and Ryser underly a reduction from partitioning tripartite graphs into triangles. This in turn is shown to be NP-complete using a recent result of Holyer.     

Algorithms for propositional model counting

We present algorithms for the propositional model counting problem #SAT. The algorithms utilize tree decompositions of certain graphs associated with the given CNF formula; in particular we consider primal, dual, and incidence graphs. We describe the algorithms coherently for a direct comparison and with sufficient detail for making an actual implementation reasonably easy. We discuss several aspects of the algorithms including worst-case time and space requirements.     

Low complexity algorithms for optimal consumer push-pull partial covering in the plane

This paper considers a model for locating a consumer within a bounded region in the plane with respect to a set of n existing pull-push suppliers. The objective is to maximize the difference of total profits and costs incurred due to the partial covering of the consumer by the suppliers pull and push influence areas. We develop efficient polynomial time algorithms for the resulting problems in the rectilinear and the Euclidean planes where the bounded region is either a rectangle or a constant size polygon, respectively. Based on these solutions, we develop algorithms for evaluating efficiently the objective function at any possible location of the consumer inside the bounded region. We also employ the algorithms for the Euclidean optimization problem and the rectilinear query computation to solve efficiently their corresponding dynamic versions, where an appearance of a new supplier or an absence of an existing one occurs. Being easy to implement due to the extensive use of simple data structures, such as the balanced and binary segment tree, and the employment of standard mechanisms, such as the sweep line, the Voronoi diagram and the circular ray shooting, our solutions potentially have wide usability.     

On the computational complexity of partial covers of Theta graphs

By use of elementary geometric arguments we prove the existence of a special integral solution of a certain system of linear equations. The existence of such a solution then yields the NP-hardness of the decision problem on the existence of locally injective homomorphisms to Theta graphs with three distinct odd path lengths.     

The complexity of partial match retrieval in a dynamic setting

The partial match retrieval problem analyzed in this paper is described as follows. Given a positive integer d, a record having d binary attributes consists of a d dimensional binary vector, referred to as the record's key, and a quantity which lies in a commutative semigroup, referred to as the value of the record. Given a set of such records having distinct keys, a partial match query is a request for the sum of the values of all records in the set whose keys lie in a hyperrectangle specified by the query. We consider the problem of designing data structures which permit insertions and deletions of records, and partial match queries. Among our results is the following. There exist data structures which accommodate arbitrary sequences of N manipulations (insertions, deletions, and queries) in (worst case) time approximately (1.226)^dN. Moreover, relative to an appropriate model of computation, this complexity is best possible.     

Algorithms for generating arguments and counterarguments in propositional logic

A common assumption for logic-based argumentation is that an argument is a pair 〈Φ,α〉 where Φ is minimal subset of the knowledgebase such that Φ is consistent and Φ entails the claim α. Different logics provide different definitions for consistency and entailment and hence give us different options for formalising arguments and counterarguments. The expressivity of classical propositional logic allows for complicated knowledge to be represented but its computational cost is an issue. In previous work we have proposed addressing this problem using connection graphs and resolution in order to generate arguments for claims that are literals. Here we propose a development of this work to generate arguments for claims that are disjunctive clauses of more than one disjunct, and also to generate counteraguments in the form of canonical undercuts (i.e. arguments that with a claim that is the negation of the conjunction of the support of the argument being undercut).     

Functional calculi of second-order elliptic partial differential operators with bounded measurable coefficients

Consider a second-order elliptic partial differential operatorL in divergence form with real, symmetric, bounded measurable coefficients, under Dirichlet or Neumann conditions on the boundary of a strongly Lipschitz domain Ω. Suppose that 1 <p < ∞ and μ > 0. ThenL has a bounded H_∞ functional calculus in L^p(Ω), in the sense that ¦¦f (L +cI)u¦¦_p ≤C sup_¦arλ¦<μ ^¦f¦ ¦‖u¦‖_p for some constantsc andC, and all bounded holomorphic functionsf on the sector ¦ argλ¦ < μ that contains the spectrum ofL +cI. We prove this by showing that the operatorsf(L + cI) are Calderón-Zygmund singular integral operators.     

A proof-search procedure for intuitionistic propositional logic

A sequent root-first proof-search procedure for intuitionistic propositional logic is presented. The procedure is obtained from modified intuitionistic multi-succedent and classical sequent calculi, making use of Glivenko’s Theorem. We prove that a sequent is derivable in a standard intuitionistic multi-succedent calculus if and only if the corresponding prefixed-sequent is derivable in the procedure.     

A new algorithm for the propositional satisfiability problem

A new enumeration algorithm is proposed for the propositional satisfiability problem. Such algorithm is based on a hypergraph formulation of the problem. Two different implementations of the algorithm are presented together with the results of an experimentation intended to compare their performance with the performance of other known methods. The computational results obtained are quite promising.