We present a theory of proof denotations in classical propositional logic. The abstract
definition is in terms of a semiring of weights, and two concrete instances are explored. With …

Let H be a proof system for quantified propositional calculus (QPC). We define the Σ qj-
witnessing problem for H to be: given a prenex Σ qj-formula A, an H-proof of A, and a truth …

We study the extension of the theory S1 2 by instances of the dual (onto) weak pigeonhole
principle for p-time functions, dWPHP (PV) x x2. We propose a natural framework for …

As an increasing number of digital library projects embrace the harvesting of item-level
descriptive metadata, issues of description granularity and concerns about potential loss of …

This paper studies the relative efficiency of variations of a tableau method for Boolean circuit
satisfiability checking. The considered method is a nonclausal generalisation of the Davis …

We present a new answer set solver, called nomore++, along with its underlying theoretical
foundations. A distinguishing feature is that it treats heads and bodies equitably as …

This paper discusses a new algebraic proof method for general sentential logics, which is
particularly apt for finitely-many-valued logics and for PC, based on reducing polynomials …

The term``Boolean category''should be used for describing an object that is to categories
what a Boolean algebra is to posets. More specifically, a Boolean category should provide …

For every binary predicate а, there is a search problem бгв for finding, given д, any е such
that азжид й е holds. б в is said to be total if every instance д has a solution е, that is, ж д ж!" …

We consider exponentially large finite relational structures (with the universe {0, 1} n) whose
basic relations are computed by polynomial size (nO (1)) circuits. We study behaviour of …