De Morgan Dual Nominal Quantifiers Modelling Private Names in NonCommutative Logic This article explores the proof theory necessary for recommending an expressive but decidable firstorder system, named MAV1, featuring a De Morgan dual pair of nominal quantifiers. These nominal quantifiers called xe2x80x9cnewxe2x80x9d and xe2x80x9cwenxe2x80x9d are distinct from the selfdual GabbayPitts and MillerTiu nominal quantifiers. The novelty of these nominal quantifiers is they are polarised in the sense that xe2x80x9cnewxe2x80x9d distributes over positive operators while xe2x80x9cwenxe2x80x9d distributes over negative operators. This greater control of bookkeeping enables private names to be modelled in processes embedded as formulae in MAV1. The technical challenge is to establish a cut elimination result from which essential properties including the transitivity of implication follow. Since the system is defined using the calculus of structures, a generalisation of the sequent calculus, novel techniques are employed. The proof relies on an intricately designed multisetbased measure of the size of a proof, which is used to guide a normalisation technique called splitting. The presence of equivariance, which swaps successive quantifiers, induces complex interdependencies between nominal quantifiers, additive conjunction, and multiplicative operators in the proof of splitting. Every rule is justified by an example demonstrating why the rule is necessary for soundly embedding processes and ensuring that cut elimination holds.

Definability for model counting Abstract   We define and evaluate a new preprocessing technique for propositional model counting. This technique leverages definability, i.e., the ability to determine that some gates are implied by the input formula xcexa3. Such gates can be exploited to simplify xcexa3 without modifying its number of models. Unlike previous techniques based on gate detection and replacement, gates do not need to be made explicit in our approach. Our preprocessing technique thus consists of two phases: computing a bipartition    xe3x80x88  I  ,  O  xe3x80x89    of the variables of xcexa3 where the variables from O are defined in xcexa3 in terms of I, then eliminating some variables of O in xcexa3. Our experiments show the computational benefits which can be achieved by taking advantage of our preprocessing technique for model counting.