An algorithm to learn read-once threshold formulas,and transformations between learning models

We present a membership query (i.e. black box interpolation) algorithm for exactly identifying the class of read-once formulas over the basis of Boolean threshold functions. We also present a catalogue of generic transformations that can be used to convert an algorithm in one learning model into an algorithm in a different model.     

Moderate-degree tetrahedral quadrature formulas

Quadrature formulas of degrees 4 to 8 for numerical integration over the tetrahedron are constructed. The formulas are fully symmetric with respect to the tetrahedron, and in some cases are the minimum point rules with this symmetry.     

Reducing signed propositional formulas

 New strategies of reduction for finite-valued propositional logics are introduced in the framework of the TAS¹ methodology developed by the authors [1]. A new data structure, the Δ^-sets, is introduced to store information about the formula being analysed, and its usefulness is shown by developing efficient strategies to decrease the size of signed propositional formulas, viz., new criteria to detect the validity or unsatisfiability of subformulas, and a strong generalisation of the pure literal rule.     

Satisfiability of co-nested formulas

As a notion dual to Knuth's nested formulas [4], we call a boolean formula in conjunctive normal formco-nested if its clauses can be linearly ordered (sayC={c _i ;i=1,2, ...,n})so that the graphG ^cl =(XC, {xc _i ;xc _i or ¬xc _i } {c _i c _i+1;i=1, 2, ...,n}) allows a noncrossing drawing in the plane so that the circlec ₁,c ₂, ...,c _n bounds the outerface. Our main result is that maximum satisfiability of co-nested formulas can be decided in linear time.Both authors acknowledge a partial support of Ec Cooperative Action IC-1000 (project ALTEC:Algorithms for Future Technologies).     

Optimal weighted chebyshev-type quadrature formulas

A weighted quadrature formula is called of Chebyshev type if it has equal coefficients and real (but not necessarily distinct) nodes. Among such quadrature rules we construct an optimal one, i. e., one which has maximum algebraic degree of accuracy and minimum error when applied to the first power not exactly integrated. Optimal quadrature rules, typically, have multiple nodes. Their construction requires the complete solution of systems of algebraic equations involving generalized power sums. Numerical results are presented for the case of constant weight function on a finite interval, as well as for weight functions of the Hermite and Laguerre type on infinite intervals. The work of the second author was supported in part by the National Science Foundation under grant GP-36557     

New symmetric interpolatory quadrature formulas

We introduce two families of symmetric, interpolatory integration formulas on the interval [−1,1]. These formulas, related to the class of recursive monotone stable (RMS) formulas, allow the application of higher order or compound rules with an efficient reuse of computed function values. One family (SM) uses function values computed outside the integration interval, the other one (HR) uses derivative data. These formulas are evaluated using a practical test based on a tecnique for comparing automatic quadrature routine introduced by Lyness and Kaganove and improved by the authors. Work supported by CNR, Grant no. 93.00570, CT01     

新阈值函数下的小波阈值去噪

针对传统小波阈值去噪法中硬阈值函数不连续,软阈值函数有固定偏差的缺点,提出一种新的阈值函数。对Donoho的固定阈值进行改进,提出一种自适应的阈值。在Matlab环境中,分别进行了实验选取最优小波基,新阈值函数的最优参数以及新阈值函数与传统硬阈值函数,软阈值函数和折衷阈值函数的对比。实验结果表明,新的阈值函数能更有效地提高语音信号的信噪比,改进语音质量。     

Short proofs for tricky formulas

Summary The object of this paper is to demonstrate how certain tricky mathematical arguments can be encoded as short formal proofs for the propositional tautologies representing the mathematical statements. Using resolution as a base proof system for the propositional calculus, we exhibit these short proofs under resolution augmented by one of two principles: the principle of extension, originally suggested by Tseitin, and the principle of symmetry, introduced in this paper. These short proofs illustrate the power of extension and symmetry in theorem proving.The principle of extension allows the introduction of auxiliary variables to represent intermediate formulas so that the length of a proof can be significantly reduced by manipulating these variables instead of the formulas that they stand for. Symmetry, on the other hand, allows one to recognize that a tautology remains invariant under certain permutations of variable names, and use that information to avoid repeated independent derivations of intermediate formulas that are merely permutational variants of one another.First we show that a number of inductive arguments can be encoded as short formal proofs using either extension or symmetry. We provide the details for the tautologies derived by encoding the statement, An acyclic digraph on n vertices must have a source. We then consider the familiar checkerboard puzzle which asserts that a checkerboard, two of whose diagonally opposite corner squares are removed, cannot be perfectly covered with dominoes. We demonstrate short proofs for the tautologies derived from the above assertion, using extension to mimic the tricky informal argument. Finally, we consider statements asserting the Ramsey property of numbers much larger than the critical Ramsey numbers. We show that the proof of Ramsey's theorem can be imitated using the principle of symmetry to yield short proofs for these tautologies.The main theme of the paper is that both extension and symmetry are very powerful augmentations to resolution. We leave open whether either extension or symmetry can polynomially simulate the other.This work was performed while the author was with the General Electric Research Center     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is ₂ ^P-complete, answering a question posed by Kleine Büning and Zhao.     

Generalizations of matched CNF formulas

A CNF formula is called matched if its associated bipartite graph (whose vertices are clauses and variables) has a matching that covers all clauses. Matched CNF formulas are satisfiable and can be recognized efficiently by matching algorithms. We generalize this concept and cover clauses by collections of bicliques (complete bipartite graphs). It turns out that such generalization indeed gives rise to larger classes of satisfiable CNF formulas which we term biclique satisfiable. We show, however, that the recognition of biclique satisfiable CNF formulas is NP-complete, and remains NP-hard if the size of bicliques is bounded. A satisfiable CNF formula is called var-satisfiable if it remains satisfiable under arbitrary replacement of literals by their complements. Var-satisfiable CNF formulas can be viewed as the best possible generalization of matched CNF formulas as every matched CNF formula and every biclique satisfiable CNF formula is var-satisfiable. We show that recognition of var-satisfiable CNF formulas is _P ² P-complete, answering a question posed by Kleine Büning and Zhao.     

Denote CSP with Temporal Formulas

This is a sequel of [1] to give a temporal semantics to a full version of CSP,including hiding operator and nested parallelis.The semantic definition is of denotational style,and employs set of temporal formulas as denotations.The continuity is proved,when the hiding operatior is restricted to channels only with finite possible meassages.     

Algebraic proofs over noncommutative formulas

We study possible formulations of algebraic propositional proof systems operating with noncommutative formulas. We observe that a simple formulation gives rise to systems at least as strong as Frege, yielding a semantic way to define a Cook-Reckhow (i.e., polynomially verifiable) algebraic analog of Frege proofs, different from that given in Buss et al. (1997) and Grigoriev and Hirsch (2003). We then turn to an apparently weaker system, namely, polynomial calculus (PC) where polynomials are written as ordered formulas (PC over ordered formulas, for short). Given some fixed linear order on variables, an arithmetic formula is ordered if for each of its product gates the left subformula contains only variables that are less-than or equal, according to the linear order, than the variables in the right subformula of the gate. We show that PC over ordered formulas (when the base field is of zero characteristic) is strictly stronger than resolution, polynomial calculus and polynomial calculus with resolution (PCR), and admits polynomial-size refutations for the pigeonhole principle and Tseitin?s formulas. We conclude by proposing an approach for establishing lower bounds on PC over ordered formulas proofs, and related systems, based on properties of lower bounds on noncommutative formulas (Nisan, 1991).The motivation behind this work is developing techniques incorporating rank arguments (similar to those used in arithmetic circuit complexity) for establishing lower bounds on propositional proofs.     

Efficiently solving quantified bit-vector formulas

In recent years, bit-precise reasoning has gained importance in hardware and software verification. Of renewed interest is the use of symbolic reasoning for synthesising loop invariants, ranking functions, or whole program fragments and hardware circuits. Solvers for the quantifier-free fragment of bit-vector logic exist and often rely on SAT solvers for efficiency. However, many techniques require quantifiers in bit-vector formulas to avoid an exponential blow-up during construction. Solvers for quantified formulas usually flatten the input to obtain a quantified Boolean formula, losing much of the word-level information in the formula. We present a new approach based on a set of effective word-level simplifications that are traditionally employed in automated theorem proving, heuristic quantifier instantiation methods used in SMT solvers, and model finding techniques based on skeletons/templates. Experimental results on two different types of benchmarks indicate that our method outperforms the traditional flattening approach by multiple orders of magnitude of runtime.     

Converting untyped formulas to typed ones

We observe that every first-order logic formula over the untyped version of some many-sorted vocabulary is equivalent to a union of many-sorted formulas over that vocabulary. This result has as direct corollary a theorem by Hull and Su on the expressive power of active-domain quantification in the relational calculus. Received: 1 April 1998     

Computational aspects of Worm-Like-Chain interpolation formulas

We show that the polynomial Worm-Like-Chain (WLC) interpolation formula introduced in [C. Bouchiat, M.D. Wang, J.-F. Allemand, T. Strick, S.M. Block, V. Croquette, Estimating the persistence length of a Worm-Like Chain molecule from force–extension measurements, Biophys. J. 76 (1) (1999) 409–413] in order to improve data fitting with respect to the WLC interpolation formula in [C. Bustamante, J.F. Marko, E.D. Siggia, S. Smith, Entropic elasticity of lambda-phage DNA, Science 265 (1994) 1599. Technical comment] is not unique. Ill-conditioning of the over-determined linear system associated with interpolation of synthetic data from [C. Bouchiat, M.D. Wang, J.-F. Allemand, T. Strick, S.M. Block, V. Croquette, Estimating the persistence length of a Worm-Like Chain molecule from force–extension measurements, Biophys. J. 76 (1) (1999) 409–413] is highlighted. Moreover, if the coefficients in the associated polynomial correction are considered as free parameters in the least squares fitting procedure for actual experimental data, then more than one solution with a low residual can be identified. For these reasons we propose modification of the interpolation formula in [C. Bustamante, J.F. Marko, E.D. Siggia, S. Smith, Entropic elasticity of lambda-phage DNA, Science 265 (1994) 1599. Technical comment] so that, for moderate extensions, quadratic contributions are included and no additional parameters are required. We show that relative errors for the fit of synthetically generated data are less than 2% and for actual data they are comparable with and sometimes better than those obtained by using polynomial WLC interpolation formulas.