Search

The ϵ-substitution method is a technique for giving consistency proofs for theories of arithmetic. We use this technique to give a proof of the consistency of the impredicative theory ID1 using a variant of the cut-elimination formalism introduced by Mints. [ABSTRACT FROM AUTHOR]

In 2007 Cortés and Peña introduced a pivoting strategy for the Neville elimination of nonsingular sign regular matrices and called it two-determinant pivoting. Neville elimination has been very useful for obtaining theoretical and practical properties for totally positive (negative) matrices and other related types of matrices. A real matrix is said to be almost strictly sign regular if all its nontrivial minors of the same order have the same strict sign. In this paper, some nice properties related with the application of Neville elimination with two-determinant pivoting strategy to almost strictly sign regular matrices are presented. [ABSTRACT FROM AUTHOR]

We prove that if T is a complete theory with weak elimination of imaginaries, then there is an explicit bijection between strict independence relations for T and strict independence relations for Teq. We use this observation to show that if T is the theory of the Fraïssé limit of finite metric spaces with integer distances, then Teq has more than one strict independence relation. This answers a question of Adler (J Math Log 9(1):1-20, , Question 1.7). [ABSTRACT FROM AUTHOR]

The $$\Omega $$ -rule was introduced by W. Buchholz to give an ordinal-free proof of cut-elimination for a subsystem of analysis with $$\Pi ^{1}_{1}$$ -comprehension. W. Buchholz's proof provides cut-free derivations by familiar rules only for arithmetical sequents. When second-order quantifiers are present, they are introduced by the $$\Omega $$ -rule and some residual cuts are not eliminated. In the present paper, we introduce an extension of the $$\Omega $$ -rule and prove the complete cut-elimination by the same method as W. Buchholz: any derivation of arbitrary sequent is transformed into its cut-free derivation by the standard rules (with induction replaced by the $$\omega $$ -rule). In fact we treat the subsystem of $$\Pi ^{1}_{1}$$ -CA (of the same strength as $$ID_{1}$$ ) that W. Buchholz used for his explanation of G. Takeuti's finite reductions. Extension to full $$\Pi ^{1}_{1}$$ -CA is planned for another paper. [ABSTRACT FROM AUTHOR]

This paper proposes an unambiguous correlation function applicable to generic sine-phased binary offset carrier (BOC) signal tracking. In the proposed scheme, first, we view the BOC sub-carrier pulse as a sum of multiple rectangular pulses. Then, we obtain partial correlation functions by correlating the multiple rectangular pulses with the received signal, and subsequently, construct two symmetric correlation functions by combining the partial correlation functions in a specialized way. Finally, we generate an unambiguous correlation function by combining the two symmetric correlation functions. The proposed correlation function has a sharper main-peak, and consequently, provides a better tracking performance than those of the conventional correlation functions in terms of the tracking error standard deviation (TESD). [ABSTRACT FROM AUTHOR]

A real matrix A = ( a i j ) 1 ≤ i , j , ≤ n is said to be almost strictly totally negative if it is almost strictly sign regular with signature ε = ( − 1 , − 1 , … , − 1 ) , which is equivalent to the property that all its nontrivial minors are negative. In this paper an algorithmic characterization of nonsingular almost strictly totally negative matrices is presented. [ABSTRACT FROM AUTHOR]

Abstract: In Gaussian elimination it is often desirable to preserve existing zeros (sparsity). This is closely related to perfect elimination schemes on graphs. Such schemes can be found in polynomial time. Gaussian elimination uses a pivot for each column, so opportunities for preserving sparsity can be missed. In this paper we consider a more flexible process that selects a pivot for each nonzero to be eliminated and show that recognizing matrices that allow such perfect partial elimination schemes is NP-hard. [Copyright &y& Elsevier]

Abstract: One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal. [Copyright &y& Elsevier]

This work addresses the inverse problems of expanded motion and path generation for the spatial (revolute–revolute–spherical–spherical, RRSS) linkage and the 4R spherical linkage with order and branch elimination. Two constrained non-linear equation systems are presented in this work for RRSS and 4R spherical motion and path generation with order and branching constraints. Both equation systems include the spatial four-link displacement model (by Suh and Radcliffe) as an objective function along with order and branching inequality constraints. As examples, both a branch defect-free and order defect-free RRSS linkage 4R spherical linkage are synthesized to approximate expanded groups of precision positions. [ABSTRACT FROM PUBLISHER]

Abstract: We describe a nonlinear technique to eliminate oscillations appearing in the discretization of diffusion operators with hybrid schemes. [Copyright &y& Elsevier]

Abstract: Our aim is to find one class of planar rational involutions of the form where , and and denote two lines, and respectively. We give necessary and sufficient conditions on the 12 parameters , such that is an involution. [Copyright &y& Elsevier]

Abstract: In this paper we show that the intuitionistic theory for finitely many iterations of strictly positive operators is a conservative extension of Heyting arithmetic. The proof is inspired by the quick cut-elimination due to G. Mints. This technique is also applied to fragments of Heyting arithmetic. [Copyright &y& Elsevier]

Abstract: A sequent calculus for Odintsov’s Hilbert-style axiomatization of a logic related to the trilattice of generalized truth values is introduced. The completeness theorem w.r.t. a simple semantics for is proved using Maehara’s decomposition method that simultaneously derives the cut-elimination theorem for . A first-order extension of and its semantics are also introduced. The completeness and cut-elimination theorems for are proved using Schütte’s method. [Copyright &y& Elsevier]

This paper provides a first example of a model theoretically well-behaved structure consisting of a proper o-minimal expansion of the real field and a dense multiplicative subgroup of finite rank. Under certain Schanuel conditions, a quantifier elimination result will be shown for the real field with an irrational power function xτ and a dense multiplicative subgroup of finite rank whose elements are algebraic over ℚ(τ). Moreover, every open set definable in this structure is already definable in the reduct given by just the real field and the irrational power function. [ABSTRACT FROM AUTHOR]

We show that, for arbitrary quantum feedback networks consisting of several quantum mechanical components connected by quantum fields, the limit of adiabatic elimination of fast oscillator modes in the components and the limit of instantaneous transmission along internal quantum field connections commute. The underlying technique is to show that both limits involve a Schur complement procedure. The result shows that the frequently used approximations, for instance, to eliminate strongly coupled optical cavities, are mathematically consistent. [ABSTRACT FROM AUTHOR]

Abstract: The Steiner Tree Problem with Delays (STPD) is a variant of the well-known Steiner Tree Problem in which the delay on each path between a source node and a terminal node is limited by a given maximum value. We propose a Branch-and-Cut algorithm for solving this problem using a formulation based on lifted Miller-Tucker-Zemlin subtour elimination constraints. The effectiveness of the proposed algorithm is assessed through computational experiments carried out on dense benchmark instances. [ABSTRACT FROM AUTHOR]

Abstract: We develop a general algebraic and proof-theoretic study of substructural logics that may lack associativity, along with other structural rules. Our study extends existing work on (associative) substructural logics over the full Lambek Calculus (see, for example, Ono (2003) , Galatos and Ono (2006) , Galatos et al. (2007) ). We present a Gentzen-style sequent system that lacks the structural rules of contraction, weakening, exchange and associativity, and can be considered a non-associative formulation of . Moreover, we introduce an equivalent Hilbert-style system and show that the logic associated with and is algebraizable, with the variety of residuated lattice-ordered groupoids with unit serving as its equivalent algebraic semantics. Overcoming technical complications arising from the lack of associativity, we introduce a generalized version of a logical matrix and apply the method of quasicompletions to obtain an algebra and a quasiembedding from the matrix to the algebra. By applying the general result to specific cases, we obtain important logical and algebraic properties, including the cut elimination of and various extensions, the strong separation of , and the finite generation of the variety of residuated lattice-ordered groupoids with unit. [Copyright &y& Elsevier]

Abstract: We study adjunct-elimination results for Context Logic applied to trees, following previous results by Lozes for Separation Logic and Ambient Logic. In fact, it is not possible to prove such elimination results for the original single-holed formulation of Context Logic. Instead, we prove our results for multi-holed Context Logic. [Copyright &y& Elsevier]

Abstract: This paper studies the forward kinematics of a symmetrical 6-6 Stewart platform, in which both the base and the mobile platform are hexagons and the joint centers satisfy some conditions. A concise algebraic elimination algorithm to solve the closed-form forward kinematics of the Stewart platform is presented. Based on the presented algebraic method, an interesting result that comes out of our study is that the forward kinematics problem is reduced to solve a univariate polynomial equation of degree at most 14. The 14th degree univariate polynomial is derived from the determinant of the 15×15 Sylvester’s matrix, which is relatively small in size, without factoring out or deriving the greatest common divisor. The algorithm is comparatively concise and requires fairly less computation time. The result is verified by a numerical example. [Copyright &y& Elsevier]

Abstract: We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases. Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas. Then we consider the so-called online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred). [Copyright &y& Elsevier]

Abstract: An improved algorithm, together with its implementation, is presented for the automatic computation of the complete root classification of a real parametric polynomial. The algorithm offers improved efficiency and a new test for non-realizable conditions. The improvement lies in the direct use of ‘sign lists’, obtained from the discriminant sequence, rather than ‘revised sign lists’. It is shown that the discriminant sequences, upon which the sign lists are based, are closely related both to Sturm–Habicht sequences and to subresultant sequences. Thus calculations based on any of these quantities are essentially equivalent. One particular application of complete root classifications is the determination of the conditions for the positive definiteness of a polynomial, and here the new algorithm is applied to a class of sparse polynomials. It is seen that the number of conditions for positive definiteness remains surprisingly small in these cases. [Copyright &y& Elsevier]

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]

The aim of this article is Schröder's treatment of the so called solution problem [Auflösungsproblem]. First, I will introduce Schröder's ideas; then I will discuss them taking into account Peirce's considerations in The Logic of Relatives ([13, pp. 161-217] now republished in [9, pp. 288-345]). [ABSTRACT FROM AUTHOR]

Abstract: A numerical elimination method is presented in this paper for floating-point computation in polynomial algebra. The method is designed to calculate one or more polynomials in an elimination ideal by a sequence of matrix rank/kernel computation. The method is reliable in numerical computation with verifiable stability and a sensitivity measurement. Computational experiment shows that the method possesses significant advantages over classical resultant computation in numerical stability and in producing eliminant polynomials with lower degrees and fewer extraneous factors. The elimination algorithm combined with an approximate GCD finder appears to be effective in solving polynomial systems for positive dimensional solutions. [Copyright &y& Elsevier]

A double-elimination tournament (DET) eliminates a team only when the team has lost twice. It is a viable alternative to a single-elimination tournament when we have time for more matches, or we wish every team to have more than one chance to demonstrate its ability. Despite its popularity, DETs have not been studied thoroughly. In this paper we propose a new DET as an alternative to the commonly Used DET This new format makes the tournament shorter, allows the better teams to play more matches, and makes most matches more competitive. Furthermore, the best team has a higher probability to win the championship in most cases. The new DET has many advantages when compared with the current FIFA World Cup™ tournament which requires approximately the same number of matches. [ABSTRACT FROM AUTHOR]

Abstract: Dirichlet degrees of freedom are often eliminated from discretized initial value boundary value equations. This has advantages (creation of a symmetric system of equations and simplification of the equations) and a potential disadvantage (modification of the equations could lead to a more complex and less convenient implementation). This paper demonstrates that no elimination is needed to keep all elimination-related advantages – if one uses standard iterative solution techniques in a proper manner. [Copyright &y& Elsevier]

Abstract: Let be a field of characteristic zero, any positive integer and let be the derivation of the polynomial ring in variables over . A Conjecture of Nowicki (Conjecture 6.9.10 in [Nowicki, A. 1994. Polynomial derivations and their rings of constants, Wydawnictwo Uniwersytetu Mikolaja Kopernika, Torun]) states the following in which case we say that is standard. In this paper, we use the elimination theory of Groebner bases to prove that Nowicki’s conjecture holds in the more general case of the derivation , . In [Kojima, H. Miyanishi, M. 1997. On Robert’s counterexample to the fourteenth problem of Hilbert, J. Pure Appl. Algebra 122, 277–292], Kojima and Miyanishi argued that is standard in the case where () for some . Although the result is true, we show in this paper that their proof is not complete. [Copyright &y& Elsevier]

In this paper we show some non-elementary speed-ups in logic calculi: Both a predicative second-order logic and a logic for fixed points of positive formulas are shown to have non-elementary speed-ups over first-order logic. Also it is shown that eliminating second-order cut formulas in second-order logic has to increase sizes of proofs super-exponentially, and the same in eliminating second-order epsilon axioms. These are proved by relying on results due to P. Pudlák. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Abstract: A real matrix A, of size , is called totally nonnegative (totally positive) if all its minors are nonnegative (positive). A variant of the Neville elimination process is studied in relation to the existence of a totally nonnegative elementary bidiagonal factorization of A. The class of quasi- oscillatory rectangular matrices, which in the square case contains the oscillatory matrices, is introduced and a characterization of this class of matrices, by incorporating bidiagonal factorization, is showed. [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]

A mechanism for combining any two substructural logics (e.g. linear and intuitionistic logics) is studied from a proof-theoretic point of view. The main results presented are cut-elimination and simulation results for these combined logics called synthesized substructural logics. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

The theory of algebraically closed non-Archimedean valued fields is proved to eliminate quantifiers in an analytic language similar to the one used by Cluckers, Lipshitz, and Robinson. The proof makes use of a uniform parameterized normalization theorem which is also proved in this paper. This theorem also has other consequences in the geometry of definable sets. The method of proving quantifier elimination in this paper for an analytic language does not require the algebraic quantifier elimination theorem of Weispfenning, unlike the customary method of proof used in similar earlier analytic quantifier elimination theorems. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [ABSTRACT FROM AUTHOR]

Hilbert's ɛ-calculus is based on an extension of the language of predicate logic by a term-forming operator ex. Two fundamental results about the ɛ-calculus, the first and second epsilon theorem, play a rôle similar to that which the cut-elimination theorem plays in sequent calculus. In particular, Herbrand's Theorem is a consequence of the epsilon theorems. The paper investigates the epsilon theorems and the complexity of the elimination procedure underlying their proof, as well as the length of Herbrand disjunctions of existential theorems obtained by this elimination procedure. [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]

Iterated elimination of strictly dominated strategies is an order dependent procedure. It can also generate spurious Nash equilibria, fail to converge in countable steps, or converge to empty strategy sets. If best replies as well-defined, then spurious Nash equilibria cannot appear; if strategy spaces are compact and payoff functions are uppersemicontinuous in own strategies, then order does not matter; if strategy sets are compact and payoff functions are continuous in all strategies, then a unique and nonempty maximal reduction exists. These positive results extend neither to the better-reply secure games for which Reny has established the existence of a Nash equilibrium, nor to games in which (under iterated eliminations) any dominated strategy has an undominated dominator. [ABSTRACT FROM AUTHOR]

Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified. [ABSTRACT FROM AUTHOR]

We apply the 2-sequents approach to the analysis of several calculi derived from linear logic. We present a uniform formal system for Linear Logic, Elementary Linear Logic and Light Linear Logic. In particular, the 2-sequent approach simplifies the syntax of Light and Elementary Linear Logic.Keywords:Sequent calculus, 2-sequents, Linear Logic, Polynomial cut-elimination, Elementary cut-elimination, Light Linear Logic, Elementary Linear Logic [ABSTRACT FROM PUBLISHER]

Variable selection is ubiquitous in statistical practice. Forward selection, backwards elimination, or a combination thereof are among the most popular techniques. Statistical texts teach direct interpretation of coefficients after variable selection. For scientific purposes, the desired interpretation is unconditional on the variable selection. In this article an influence analysis of variable selection is performed from a Bayesian viewpoint. Variable selection is shown to be surprisingly influential. A new statistic is recommended for routine examination during variable selection. [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.

The article focuses on the philosophical significance of the sequent calculus. It is stated that in a sequent calculus, the objects that are manipulated in proofs are not formulas, but sequents. It is mentioned that the operational rules of a sequent calculus are related to particular logical operations; and these rules can be divided into introduction and elimination rules.

Tabu search is a metastrategy for guiding known heuristics to overcome local optimality. Successful applications of this kind of metaheuristic to a great variety of problems have been reported in the literature. However, up to now mainly static tabu list management ideas have been applied. In this paper we describe a dynamic strategy, the reverse elimination method, and give directions on improving its computational effort. The impact of the method will be shown with respect to a multiconstraint version of the zero--one knapsack problem. Numerical results are presented comparing it with a simulated annealing approach. [ABSTRACT FROM AUTHOR]