We present several experimental algorithms for fast computation of variadic polynomials over non-negative integers.

We investigate the complexity of three optimization problems in Boolean propositional logic related to information theory: Given a conjunctive formula over a set of relations, find a satisfying assignment with minimal Hamming distance to a given assignment that satisfies the formula ( NearestOtherSolution , NOSol ) or that does not need to satisfy it ( NearestSolution , NSol ). The third problem asks for two satisfying assignments with a minimal Hamming distance among all such assignments ( MinSolutionDistance , MSD ). For all three problems we give complete classifications with respect to the relations admitted in the formula. We give polynomial time algorithms for several classes of constraint languages. For all other cases we prove hardness or completeness regarding APX, poly-APX, or equivalence to well-known hard optimization problems.

Let Γ be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in Γ is in LogSpace or complete for the class CSP(Γ)NP under deterministic polynomial-time many-one reductions. Here, CSP(Γ)NP is the class of problems that can be reduced to the constraint satisfaction problem of Γ under non-deterministic polynomial-time many-one reductions.

We study the complexity of the propositional minimal inference problem. Its complexity has been extensively studied before because of its fundamental importance in artificial intelligence and nonmonotonic logics. We prove that the complexity of the minimal inference problem with unbounded queries has a trichotomy (between P, coNP-complete, and Pi2P-complete). This result finally settles with a positive answer the trichotomy conjecture of Kirousis and Kolaitis[A dichotomy in the complexity of propositional circumscription, LICS'01] in the unbounded case. We also present simple and efficiently computable criteria separating the different cases.

Given a finite set of vectors over a finite totally ordered domain, we study the problem of computing a constraint in conjunctive normal form such that the set of solutions for the produced constraint is identical to the original set. We develop an efficient polynomial-time algorithm for the general case, followed by specific polynomial-time algorithms producing Horn, dual Horn, and bijunctive formulas for sets of vectors closed under the operations of conjunction, disjunction, and median, respectively. Our results generalize the work of Dechter and Pearl on relational data, as well as the papers by Hébrard and Zanuttini. They complement the results of Hähnle et al. on multivalued logics and Jeavons et al. on the algebraic approach to constraints.

Two main applications of term rewriting systems are equational reasoning in theorem provers and equational computation in programming languages. The present paper examines a number of term rewriting systems in terms of how rewriting is used in different implementations of theorem provers, the use of rewriting techniques in logic programming languages and the problem of efficiency. In addition a non-exhaustive catalogue of distributed implementations is presented.

Abstract This article introduces a generalisation of the crossed rule approach to the detection of Knuth-Bendix completion procedure divergence. It introduces closure chains, which are special rule closures constructed by means of particular substitution operations and operators, as a suitable formalism for progress in this direction. Supporting substitution algebra is developed first, followed by considerations concerning rule closures in general, concluding with an investigation of closure chain properties. Issues concerning the narrowing process are not discussed here.