Search

Abstract: We first look at an existing infinitary sequent system for common knowledge for which there is no known syntactic cut-elimination procedure and also no known non-trivial bound on the proof-depth. We then present another infinitary sequent system based on nested sequents that are essentially trees and with inference rules that apply deeply inside these trees. Thus we call this system “deep” while we call the former system “shallow”. In contrast to the shallow system, the deep system allows one to give a straightforward syntactic cut-elimination procedure. Since both systems can be embedded into each other, this also yields a syntactic cut-elimination procedure for the shallow system. For both systems we thus obtain an upper bound of on the depth of proofs, where is the Veblen function. [Copyright &y& Elsevier]

Abstract: This paper proves the strong normalization of classical natural deduction with disjunction and permutative conversions, by using CPS-translation and augmentations. Using them, this paper also proves the strong normalization of classical natural deduction with general elimination rules for implication and conjunction, and their permutative conversions. This paper also proves that natural deduction can be embedded into natural deduction with general elimination rules, strictly preserving proof normalization. [Copyright &y& Elsevier]

Abstract: A simple cut elimination proof for arithmetic with the epsilon symbol is used to establish the termination of a modified epsilon substitution process. This opens a possibility of extension to much stronger systems. [Copyright &y& Elsevier]

Abstract: For a tree T and an integer , it is well known that the kth power of T is strongly chordal and hence has a strong elimination ordering of its vertices. In this note we obtain a complete characterization of strongly simplicial vertices of , thereby characterizing all strong elimination orderings of the vertices of . [Copyright &y& Elsevier]

Abstract: Epistasis is the interaction between two or more genes to control a single phenotype. We model epistasis with a two-locus two-allele problem. The resulting model allows us to examine both population sizes as well as genotypic and phenotypic frequencies. In the context of an example, we show that if epistasis results in an undesirable phenotype, such as a genetically transmitted disease or condition, elimination of undesirable phenotypes from the population through selective breeding may be possible, although such selective breeding could lead to an increase in less desirable phenotypes and possibly the elimination of desirable phenotypes. [Copyright &y& Elsevier]

The standard rule of necessitation in systems of natural deduction for the modal logic S4 concludes □A from A whenever all assumptions A depends on are modal formulas. This condition prevents the composability and normalization of derivations, and therefore modifications of the rule have been suggested. It is shown that both properties hold if, instead of changing the rule of necessitation, all elimination rules are formulated in the manner of disjunction elimination, i.e. with an arbitrary consequence. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract: The rotating-wave approximation (RWA) is a formalism of great utility in the description of the coherent excitation of atoms and molecules by laser light. Not only does it give results in agreement with experiment, it also provides a simple framework allowing the Hamiltonian of a system to be written down from inspection of the state-linkage diagram. Recent interest in systems with a two-photon coupling prompted an investigation of the structure of two-photon terms in RWA Hamiltonians. In carrying through the derivation, an interaction with adiabatic elimination was discovered. It is shown that adiabatic elimination must be performed before application of the RWA, else terms are dropped that ought to be retained. RWA Hamiltonians for three-state systems with one and two two-photon linkages are displayed. [Copyright &y& Elsevier]

An n × m real matrix A is a totally positive matrix if all its minors are nonnegative. The Neville elimination process is studied in relation to the existence of a totally positive factorization LS of a rectangular matrix. An LS factorization is obtained for a totally positive matrix, where L is a lower echelon form matrix, of size n × k, and S is an upper echelon form matrix, of size k × m, and both L and S are totally positive matrices. [ABSTRACT FROM AUTHOR]

Based on the computation mode introduced in [13], we deal with the time complexity of computations over arbitrary first-order structures.The main emphasis is on parameter-free computations. Some transfer results for solutions of P versus NP problems as well as relationships to quantifier elimination are discussed. By computation tree analysis using first-order formulas, it follows that P versus NP solutions and other results of structural complexity theory are invariant under elementary equivalence of structures. [ABSTRACT FROM AUTHOR]

The article describes a modification of LD and proves the cut-elimination theorem for it. It establishes a weak version of cut-elimination theorem for LD, stating that all cuts except some special forms can be eliminated from a proof in LD. It obtains some corollaries on syntactical properties of CD from these cut-elimination theorems.

Discusses the application of a cut-elimination theorem of mathematician Gerhard Gentzen in the alpha graphs logic of philosopher Charles Peirce. Infinite supply of atomic formulas; Even elimination and odd introduction as rules of inference; Overview of the rule of insertion and deletion.

Valentini (1983) has presented a proof of cut-elimination for provability logic GL for a sequent calculus using sequents built from sets as opposed to multisets, thus avoiding an explicit contraction rule. From a formal point of view, it is more syntactic and satisfying to explicitly identify the applications of the contraction rule that are ‘hidden’ in proofs of cut-elimination for such sequent calculi. There is often an underlying assumption that the move to a proof of cut-elimination for sequents built from multisets is straightforward. Recently, however, it has been claimed that Valentini’s arguments to eliminate cut do not terminate when applied to a multiset formulation of the calculus with an explicit rule of contraction. The claim has led to much confusion and various authors have sought new proofs of cut-elimination for GL in a multiset setting.Here we refute this claim by placing Valentini’s arguments in a formal setting and proving cut-elimination for sequents built from multisets. The use of sequents built from multisets enables us to accurately account for the interplay between the weakening and contraction rules. Furthermore, Valentini’s original proof relies on a novel induction parameter called “width” which is computed ‘globally’. It is difficult to verify the correctness of his induction argument based on “width.” In our formulation however, verification of the induction argument is straightforward. Finally, the multiset setting also introduces a new complication in the case of contractions above cut when the cut-formula is boxed. We deal with this using a new transformation based on Valentini’s original arguments.Finally, we discuss the possibility of adapting this cut-elimination procedure to other logics axiomatizable by formulae of a syntactically similar form to the GL axiom. [ABSTRACT FROM AUTHOR]

Single elimination tournaments are used as a context for illustrating some basic probability concepts. An algorithm which automatically constructs a tournament, given team seeding, is presented. Probabilities of winning are calculated as a function of team seed and strength, both of which are selected by the user. This technique allows for easy experimentation to see how the interaction of seeding and strength affects probabilities of winning. Users may also select a particular team to win up to a predetermined round in order to see the resulting changes in probabilities. Some examples with surprising results are used to illustrate how probabilities can change. [ABSTRACT FROM AUTHOR]

The EUREF permanent network (EPN) is a network of continuously operating global navigation satellite system (GNSS) stations, primarily installed for reference frame maintenance. In order to ensure the long term reliability of the EPN products, a thorough station performance monitoring has been initiated and carried out in addition to the routine GNSS data management, processing and analysis. This paper addresses the main factors influencing the quality of the coordinate time series in a permanent GNSS network. Relevant examples, based on the EPN experience are given, the analysis strategy is introduced, the estimated coordinate offsets are published and the importance of this analysis for site velocity estimation is demonstrated. The results are derived from the analysis of the EPN weekly combined solutions covering the period from 1996 to 2003. Our target is the identification, interpretation and elimination of offsets and outliers present in the EPN coordinate time series in order to estimate reliable coordinates and velocities and consequently maintain a high quality kinematic reference network. [ABSTRACT FROM AUTHOR]

Let D be a diagonal matrix and Eij denote the n-by-n matrix with a 1 in entry (i,j) and 0 in every other entry. An n-by-n matrix A has a successively ordered elementary bidiagonal (SEB) factorization if it can be factored as [This symbol cannot be presented in ASCII format] in which Lj(sjk) = I + sjkEj,j -1 and Uj(tkj) = I + tkjEj -1,j for some scalars sjk,tkj. Note that some of the parameters sjk,tkj may be zero, and the order of the bidiagonal factors is fixed. If this factorization corresponds to reduction of A to D via successive row/column operations in the specified order, it is called an elimination SEB factorization. New rank conditions are formulated that are proved to be necessary and sufficient for matrix A to have such a factorization. These conditions are related to known but more restrictive properties that ensure a bidiagonal factorization as above, but with all parameters sjk,tkj nonzero. [ABSTRACT FROM AUTHOR]

Recently Ekman gave a derivation in natural deduction such that it either contains a substantial redundant part or else is not normal. It is shown that this problem is caused by a non-normality inherent in the usual modus ponens rule. [ABSTRACT FROM AUTHOR]

Let R be an arbitrary Euclidean domain and A be an n×n matrix of determinant 1 whose entries are elements of R. Gaussian elimination process based on Euclidean division algorithm (on R) allows one to write A as a product of elementary matrices over R. Suslin's stability theorem states that any n×n multivariate polynomial matrix of determinant 1 with n 3 can be written as a product of elementary matrices. This result fails when n = 2, and a counter-example was constructed by P. M. Cohn [Inst. Hautes ´ Etudes Sci. Publ. Math. 30 (1996), pp. 365­413]. In this paper, an algorithm is developed that determines precisely when a given matrix in SL2(R[x1,...,xm]) allows a factorization into elementary matrices and, if it does, expresses it as a product of elementary matrices. This algorithm has potential applications to signal processing, in which case the coefficient ring R is usually taken as a field or a ring Z of integers. Extending the idea used in this algorithm, we disprove a conjecture of Tolhuizen­Hollmann­Kalker regarding the realizability of a certain FIR filter. [ABSTRACT FROM AUTHOR]

We study backward elimination (BE) and multiple comparisons (MC) in a general linear model. The usual BE method based on partial correlations is equivalent to the MC statistics for the corresponding regression coefficients. In addition, it is shown that, typically, the usual MC statistics for the general MC problem are equivalent to partial correlations for BE. To obtain P values and critical values in BE and MC one needs to compute probabilities for the minimum and maximum of absolute values of correlated t variables. We investigate algorithms that can efficiently compute upper and lower bounds based on second-order Bonferroni inequalities and are capable of handling a large number of variables and comparisons. To be specific, consider a linear normal model with full rank, expressed in the form y[(sub n x 1)] = X[(sub n x p)] x theta[(sub p x 1]) + Z[(n x q)] x delta [(q x 1]) epsilon[(sub n x 1]). Two seemingly different problems are considered: (1) BE of the columns in Z, assuming that X has been forced into the model; specifically, one-step variable elimination where x[sub 1],..., x[sub p], z[sub 1],..., z[sub q] are the variables remaining in the model at the current step. The problem is to test if one of the z,'s is to be eliminated from the model or not. (2) MC of a finite number m of linear combinations of delta, c, delta for I = 1 ,..., m. Here c[sub 1] is a q x I known vector and the following multiple testing problem is considered: FI,: c[sub l] delta = 0 versus A[sub l]: c[sub l] delta is not equal to 0 for 1,..., m. The BE method is presented as a partial correlation method and related to the multiple t method for delta. Moreover, it is shown that if m is less than or equal to q then the usual MC method is also a BE method. When m > q the simultaneous MC procedure turns out to be (under a condition on c[sub 1],..., c[sub m]) equivalent to a certain type of restricted BE method, based on... [ABSTRACT FROM AUTHOR]

In view of the problem that the tracking performance declines caused by wild value from phase error discriminator, this paper proposes a new method of wild value elimination. The method adaptively regulates elimination threshold for wild value based on the range of phase error discrimination and loop state of code tracking loop. Simulation results indicate that the principle of the method is correct and it performs well for code tracking loop. Compared with the normal code tracking loop, it is seen that the loop using this method has high precision and strong antijamming capacity. [ABSTRACT FROM AUTHOR]

Abstract: In this article, we study using model theory certain classes of real functions: restricted quasi-analytic classes. Let E be such a class of functions, we introduce a natural language , including E and a theory T in such that T admits quantifiers elimination, is o-minimal and is equivalent to the complete theory of in . To cite this article: A. Rambaud, C. R. Acad. Sci. Paris, Ser. I 343 (2006). [Copyright &y& Elsevier]

Abstract: We introduce the convergence of algebraic multigrid in the form of matrix decomposition. The convergence is proved in block versions of the multi-elimination incomplete LU (BILUM) factorization technique and the approximation of their inverses to preserve sparsity. The convergence theorem can be applied to general interpolation operator. Furthermore, we discuss the error caused by the error matrix. [Copyright &y& Elsevier]

Abstract: We give inequational and equational axioms for semirings with a fixed-point operator and formally develop a fragment of the theory of context-free languages. In particular, we show that Greibach’s normal form theorem depends only on a few equational properties of least pre-fixed points in semirings, and eliminations of chain and deletion rules depend on their inequational properties (and the idempotence of addition). It follows that these normal form theorems also hold in non-continuous semirings having enough fixed points. [Copyright &y& Elsevier]

A constant scoring rule asks each individual to vote for a given (and constant) number of alternatives and the alternative with the most votes is elected. A sequential constant scoring rule applies this principle in a process of sequential elimination. Constant scoring rules as well as sequential constant scoring rules fail to satisfy Condorcet criteria when individual preferences are unrestricted. The purpose of this paper is to show that, if we assume that preferences are single-peaked, then some constant scoring rules satisfy the Condorcet loser criterion and some sequential constant scoring rules satisfy the Condorcet winner criterion. The results we provide make possible the identification of these rules. [ABSTRACT FROM AUTHOR]

Leo Harrington showed that the second-order theory of arithmetic WKL 0 is $${\Pi^1_1}$$ -conservative over the theory RCA 0. Harrington’s proof is model-theoretic, making use of a forcing argument. A purely proof-theoretic proof, avoiding forcing, has been eluding the efforts of researchers. In this short paper, we present a proof of Harrington’s result using a cut-elimination argument. [ABSTRACT FROM AUTHOR]

We give a proof of the finite model property (fmp) of some fragments of commutative and noncommutative linear logic: the Lambek calculus, BCI, BCK and their enrichments, MALL and Cyclic MALL. We essentially simplify the method used in [4] for proving fmp of BCI and the Lambek ca culus and in [5] for proving fmp of MALL. Our construction of finite models also differs from that used in Lafont [8] in his proof of fmp of MALL (we do not use cut elimination). [ABSTRACT FROM AUTHOR]