Search

We describe a new quantifier elimination algorithm for real closed fields based on Thom encoding and sign determination. The complexity of this algorithm is elementary recursive and its proof of correctness is completely algebraic. In particular, the notion of connected components of semialgebraic sets is not used. [ABSTRACT FROM AUTHOR]

In an asymmetric rendezvous system, such as an unfair synchronous queue or an elimination array, threads of two types, consumers and producers, show up and are matched each with a unique thread of the other type. Here we present new highly scalable, high throughput asymmetric rendezvous systems that outperform prior synchronous queue and elimination array implementations under both symmetric and asymmetric workloads (more operations of one type than the other). Based on this rendezvous system, we also construct a highly scalable and competitive stack implementation. [ABSTRACT FROM AUTHOR]

By a sequence of rollings without slipping or twisting along segments of a straight line of the plane, a spherical ball of unit radius has to be transferred from an initial state to an arbitrary final state taking into account the orientation of the ball. We provide a new proof that with at most 3 moves, we can go from a given initial state to an arbitrary final state. The first proof of this result is due to Hammersley ( ). His proof is more algebraic than ours which is more geometric. We also showed that 'generically' no one of the three moves, in any elimination of the spin discrepancy, may have length equal to an integral multiple of 2π. [ABSTRACT FROM AUTHOR]

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]

Abstract: In functional brain mapping, pattern recognition methods allow detecting multivoxel patterns of brain activation which are informative with respect to a subject''s perceptual or cognitive state. The sensitivity of these methods, however, is greatly reduced when the proportion of voxels that convey the discriminative information is small compared to the total number of measured voxels. To reduce this dimensionality problem, previous studies employed univariate voxel selection or region-of-interest-based strategies as a preceding step to the application of machine learning algorithms. Here we employ a strategy for classifying functional imaging data based on a multivariate feature selection algorithm, Recursive Feature Elimination (RFE) that uses the training algorithm (support vector machine) recursively to eliminate irrelevant voxels and estimate informative spatial patterns. Generalization performances on test data increases while features/voxels are pruned based on their discrimination ability. In this article we evaluate RFE in terms of sensitivity of discriminative maps (Receiver Operative Characteristic analysis) and generalization performances and compare it to previously used univariate voxel selection strategies based on activation and discrimination measures. Using simulated fMRI data, we show that the recursive approach is suitable for mapping discriminative patterns and that the combination of an initial univariate activation-based (F-test) reduction of voxels and multivariate recursive feature elimination produces the best results, especially when differences between conditions have a low contrast-to-noise ratio. Furthermore, we apply our method to high resolution (2 × 2 × 2mm3) data from an auditory fMRI experiment in which subjects were stimulated with sounds from four different categories. With these real data, our recursive algorithm proves able to detect and accurately classify multivoxel spatial patterns, highlighting the role of the superior temporal gyrus in encoding the information of sound categories. In line with the simulation results, our method outperforms univariate statistical analysis and statistical learning without feature selection. [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: The role of the base in the synthesis of 3′-deoxy-3′-[18F]fluorothymidine, [18F]FLT, via nucleophilic substitution of the nosyl group with [18F]fluoride was investigated. The rate of 18F-incorporation into the molecule dramatically changed as a function of the precursor-to-base ratio. In the presence of excess base, the precursor was consumed by elimination before substitution was complete. When the precursor-to-base ratio was optimal, an overall [18F]FLT yield of 30–40% was achieved even if the precursor amount was as small as 8–13mg. [Copyright &y& Elsevier]

Heck-type 4-exo-trigcyclization of linear 2-enol triflate-1,5-hexadienes provides functionalized methylene cyclobutanes. Intramolecular palladium coordination can initiate -hydride elimination leading to 1,2-dimethylene cyclobutane derivatives, which are obtained with high selectivity if substrates having a geminal diphenyl group at Care used. In parallel, formal 5-endo-trigcyclization and -hydride elimination form 1-methylene cyclopent-2-en derivatives. [ABSTRACT FROM AUTHOR]

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: We present a Gröbner basis associated with the symmetric group of degree , which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property. [Copyright &y& Elsevier]

A new set of conversions for derivations in the system of sequents for intuitionistic predicate logic will be defined. These conversions will be some modifications of Zucker's conversions from the system of sequents [InlineMediaObject not available: see fulltext.] from [11], which will have the following characteristics: (1) these conversions will be sufficient for transforming a derivation into a cut-free one, and (2) in the natural deduction the image of each of these conversions will be either in the set of conversions for normalization procedure, or an identity of derivations. This will be used to give a new proof of the normalization theorem for natural deduction, as a consequence of the cut-elimination theorem for the system of sequents. [ABSTRACT FROM AUTHOR]

Abstract: We introduce a system of simply typed lambda terms (with fixed point combinators) and show that a rather comprehensive class of (co-)recursion equations on streams or non-wellfounded trees can be solved in our system. Moreover certain conditions are presented which guarantee that the defined functionals are primitive recursive. As a major example we give a co-recursive treatment of Mints’ continuous cut-elimination operator. [Copyright &y& Elsevier]

Abstract: We give geometric axioms for existentially closed Hasse fields. We prove a quantifier elimination result for existentially closed -truncated Hasse fields and characterize them as reducts of existentially closed Hasse fields. [Copyright &y& Elsevier]

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]

The ground-state intramolecular gas-phase dissociation pathways of ethyl fluoroformate radical cation (FCOOCH2CH·3+) are studied using density functional molecular orbital methods. Initial geometries are optimized using the 6-31G* basis set. Electron correlation is incorporated by optimizing the geometries at the B3LYP level using the 6-31G** basis set. Stationary points are characterized by frequency calculation at the same level of theory and basis set. In the first installment of this paper, the existence of so-called enol pathway was reported and the dissociation mechanism was described in detail. In this installment, a new dissociation mechanism, a supposed keto pathway, is proposed. In this reaction channel, the ester linkage is immediately broken in a rate-determining E1 step producing FCOOꔷ and C2H·5+ which reacts further in a bimolecular elimination mechanism to yield the same intermediates (FCOOH + C2H·4+ as the enol pathway. In a similar manner as the enol pathway, the keto pathway is terminated by a slow elimination of a proton from C2H·4+ by FCOOH which acts as a base in an E2 elimination scheme. The keto pathway is more accessible than the enol pathway explaining the relative heights of the MS peaks in the EI spectrum of ethyl fluoroformate. [Copyright &y& Elsevier]

Abstract: An easy and general sequenced elimination/reduction or elimination/cyclopropanation process promoted by samarium diiodide or/and CH2I2/Sm provide an efficient method for synthesising 2,3-dideuterioamides 3 or cyclopropanamides 8, respectively. The transformations take place in high yields and with total or high selectivity from the easily available 2,3-epoxyamides. [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]

It is well known that some pivoting strategies are backward stable for Gauss elimination but are not backward stable for Gauss–Jordan elimination (GJE) when these procedures are used to solve a linear system Ax=b. We analyse the simultaneous backward stability for Gauss and GJE of several pivoting strategies, including a pivoting strategy which we call double partial pivoting. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Genera connections between quantifier elimination and decidability for first order theories are studied and exemplified. [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]

We define a reasonably well-behaved class of ultraimaginaries, i.e. classes modulo -invariant equivalence relations, called tame, and establish some basic simplicity-theoretic facts. We also show feeble elimination of supersimple ultraimaginaries: If is an ultraimaginary definable over a tuple with , then is eliminable up to rank . Finally, we prove some uniform versions of the weak canonical base property. [ABSTRACT FROM AUTHOR]

There are two distinct approaches to the study of initial value problem of the periodic box-ball systems. One way is the rigged configuration approach due to Kuniba–Takagi–Takenouchi and another way is the 10-elimination approach due to Mada–Idzumi–Tokihiro. In this paper, we describe precisely interrelations between these two approaches. [ABSTRACT FROM AUTHOR]

We introduce various sequent systems for propositional logics having strict implication, and prove the completeness theorems and the finite model properties of these systems.The cut-elimination theorems or the (modified) subformula properties are proved semantically. [ABSTRACT FROM PUBLISHER]

Synthetic differential geometry occupies a unique position in topos-theoretic physics. Nevertheless it has appeared somewhat too conceptual to physicists in general, partly because it has appeared to lack computational aspects. Its computational facets are really concerned with computation of the quasi-colimit of a finite diagram of infinitesimal spaces, or equivalently, with computation of the limit of a finite diagram of Weil algebras. Indeed we have been forced to do a highly involved computation of the above kind by hand in our previous papers (Nishimura, H. in Int. J. Theor. Phys. 36:1099–1131, and Nishimura, H. in Int. J. Theor. Phys. 38:2163–2174, ). The principal objective in this paper is to show that Grö bner bases techniques provide us with means that relegate such computations to computers. [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 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]

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: We consider the use of state elimination to construct shorter regular expressions from finite-state automata (FAs). Although state elimination is an intuitive method for computing regular expressions from FAs, the resulting regular expressions are often very long and complicated. We examine the minimization of FAs to obtain shorter expressions first. Then, we introduce vertical chopping based on bridge states and horizontal chopping based on the structural properties of given FAs. We prove that we should not eliminate bridge states until we eliminate all non-bridge states to obtain shorter regular expressions. In addition, we suggest heuristics for state elimination that leads to shorter regular expressions based on vertical chopping and horizontal chopping. [Copyright &y& Elsevier]

Abstract: Møller-Plesset MP2/6-31G method was used to examine the gas-phase elimination of 2-substituted alkyl ethyl N,N-dimethylcarbamates. The results of these calculations support a concerted non-synchronous six-membered cyclic transition state mechanism for carbamates containing a Cβ–H bond at the alkyl side of the ester. These substrates produce the N,N-dimethylcarbamic acid and the corresponding olefin. The unstable intermediate, N,N-dimethylcarbamic acid, rapidly decomposes through a four-membered cyclic transition state to dimethylamine and CO2 gas. Correlation of the logarithm of theoretical rate coefficients against original Taft''s σ* values gave an approximate straight line (ρ*=−1.39, r=0.9558 at 360°C). In addition to this fact, when log k rel is plotted against the theoretical log k rel for 2-substituted ethyl N,N-dimethylcarbamates a reasonable straight line (r=0.9919 at 360°C) is obtained, suggesting similar mechanism. [Copyright &y& Elsevier]

We give necessary and sufficient conditions on a directed graph E for which the associated Leavit path algebra L K (E) has at least one full idempotent. Also, we define E n , n ≥ 0 sub-graphs of E and show that L K (E) has at least one full idempotent if and only if there is a sub-graph E r such that the associated Leavitt path algebra L K (E r) has at least one full idempotent. [ABSTRACT FROM AUTHOR]

We devise a fast fraction-free algorithm for the computation of the triangular factorization of Bernstein–Bezoutian matrices with entries over an integral domain. Our approach uses the Bareiss fraction-free variant of Gaussian elimination, suitably modified to take into account the structural properties of Bernstein–Bezoutian matrices. The algorithm can be used to solve problems in algebraic geometry that arise in computer aided geometric design and computer graphics. In particular, an example of the application of this algorithm to the numerical computation of the intersection points of two planar rational Bézier curves is presented. Copyright © 2005 John Wiley & Sons, Ltd. [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]