Search

Abstract In this paper we calibrate the strength of the soundness of a set theory KP ω + (Π 1 -Collection) with the assumption that 'there exists an uncountable regular ordinal' in terms of the existence of ordinals. [ABSTRACT FROM AUTHOR]

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]

The sports elimination problem asks whether a team participating in a competition still has a chance to win, given the current standings and the remaining matches to be played among the teams. This problem can be viewed as a graph labelling problem, where arcs receive labels that contribute to the score of both endpoints of the arc, and the aim is to label the arcs in a way that each vertex obtains a score not exceeding its capacity. We investigate the complexity of this problem in detail, using a multivariate approach to examine how various parameters of the input graph (such as the maximum degree, the feedback vertex/edge number, and different width parameters) influence the computational tractability. We obtain several efficient algorithms, as well as certain hardness results. [ABSTRACT FROM AUTHOR]

Quantifier elimination is a foundational issue in the field of algebraic and logic computation. In first-order logic, every formula is well composed of atomic formulas by negation, conjunction, disjunction, and introducing quantifiers. It is often made quite complicated by the occurrences of quantifiers and nonlinear functions in atomic formulas. In this paper, we study a class of quantified exponential polynomial formulas extending polynomial ones, which allows the exponential to appear in the first variable. We then design a quantifier elimination procedure for these formulas. It adopts the scheme of cylindrical decomposition that consists of four phases—projection, isolation, lifting, and solution formula construction. For the non-algebraic representation, the triangular systems are introduced to define transcendental coordinates of sample points. Based on that, our cylindrical decomposition produces projections for input variables only. Hence the procedure is direct and effective. [ABSTRACT FROM AUTHOR]

This paper deals with the computational modeling and numerical simulation of contact problems at finite deformations using the finite element method. Quasi-static and dynamic problems are considered and two particular frictional conditions, full stick friction and frictionless cases, are addressed. Lagrange multipliers and regularized formulations of the contact problem, such as penalty or augmented Lagrangian methods, are avoided and a new direct elimination method is proposed. Conserving algorithms are also introduced for the proposed formulation for dynamic contact problems. An assessment of the performance of the resulting formulation is shown in a number of selected benchmark tests and numerical examples, including both quasi-static and dynamic contact problems under full stick friction and frictionless contact conditions. Conservation of key discrete properties exhibited by the time stepping algorithm used for dynamic contact problems is also shown in an example. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm called “volume & neighbors” for finding elimination trees for multifrontal solver algorithm applied to three dimensional h -adaptive finite element method computations. The algorithm is described in a pseudo-code and explained on exemplary h -refined grids. The algorithm is implemented in three dimensional h -adaptive finite element method code and tested on a sequence of representative grids, namely uniform grid, grid with point singularity, grid with edge singularity and grid with face singularity. The number of floating point operations for the multifrontal solver algorithm working with the elimination trees generated by the volume & neighbors algorithm is compared with the number of floating-point operations resulting from execution of the state-of-the-art multifrontal direct solver MUMPS with state-of-the-art algorithms for constructing elimination trees like nested-dissection from METIS library and approximate minimum degree AMD algorithm as well as PORD algorithm. In all the cases the volume & neighbors algorithm outperforms other state-of-the art algorithms. The only exception is the case of the uniform grid, where the algorithm results in a similar number of FLOPs than nested dissection algorithm. [ABSTRACT FROM AUTHOR]

Proposes a determinantal formula for the sparse resultant of an arbitrary system of n+1 polynomials in n variables. Use of a mixed polyhedral subdivision of Minkowski sum of the Newton polytopes to construct a Newton matrix; How to compute the sparse resultant for arbitrary specialization; Analysis of the worst-case asymptotic bit complexity.

Given a variety X over a perfect field, we study the partition defined on X by the multiplicity (into equimultiple points), and the effect of blowing up at smooth equimultiple centers. Over fields of characteristic zero we prove resolution of singularities by using the multiplicity as an invariant, instead of the Hilbert Samuel function. [ABSTRACT FROM AUTHOR]

Abstract: Perfect vertex elimination schemes are part of the characterizations for several classes of graphs, including chordal and cop-win. Partial elimination schemes reduce a graph to an important subgraph, for example, -cores and robber-win graphs. We are interested in those partial elimination schemes, in which once a vertex is ready to be eliminated, it stays in that state regardless of which other vertices are eliminated. We show that in such a scheme, the sets of subsets of eliminated vertices, when ordered by inclusion, form an upper locally distributed lattice. We also show that (a) unless they contain a specific induced subgraph, the cop-win orderings have this property, and that (b) the process of cleaning graphs also leads to upper locally distributed lattices. Finally, we ask for an elimination scheme, which graphs are associated with distributive lattices? [Copyright &y& Elsevier]

It needs much computation to develop a contact state graph and find an assembly sequence because polyhedral objects consist of a lot of vertices, edges, and faces. In this paper, we propose a new method to eliminate unnecessary contact states in the contact state graph corresponding to a robotic assembly task. In our method, the faces of polyhedral objects are triangulated, and the adjacency of each vertex, edge, and triangle between an initial contact state and a target contact state is defined. Then, this adjacency is used to create contact state graphs at different priorities. When a contact state graph is finished at a higher priority, a lot of unnecessary contact states can be eliminated because the contact state graph already includes at least one realizable assembly sequence. Our priority-based method is compared with a face-based method through statistically analyzing the contact state graphs obtained from different assembly tasks. Finally, our method results in a significant improvement in the final performance. [ABSTRACT FROM AUTHOR]

This paper shows that for any given polynomial ideal the collection of Gröbner cones corresponding to -specific elimination orders forms a star-shaped region which contrary to first intuition in general is not convex. Moreover we show that the corresponding region may contain Gröbner cones intersecting in the boundary of the Gröbner fan in the origin only. This implies that Gröbner walks aiming for the elimination of variables from a polynomial ideal can be terminated earlier than previously known. We provide a slightly improved stopping criterion for a known Gröbner walk algorithm for the elimination of variables. [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: We present an alternative explicit expression for the Moore–Penrose inverse of a matrix. Based on this expression, we propose a Gauss–Jordan elimination method for the computation of . Its computational complexity indicates that this method is more efficient than the existing Gauss–Jordan elimination method in the literature for a large class of problems. An example is included to illustrate the new method. [Copyright &y& Elsevier]

Abstract: Neville elimination is a direct method for the solution of linear systems of equations with advantages for some classes of matrices and in the context of pivoting strategies for parallel implementations. The growth factor is an indicator of the numerical stability of an algorithm. In the literature, bounds for the growth factor of Neville elimination with some pivoting strategies have appeared. In this work, we determine all the matrices such that the minimal upper bound of the growth factor of Neville elimination with those pivoting strategies is reached. [Copyright &y& Elsevier]

We introduce a method of reducing the q-Member p-Committee Problem for an arbitrary finite system of sets to the same problem for a system of sets of smaller size and with a smaller number of subsystems with nonempty intersection maximal with respect to inclusion. For p = 1/2, for an infeasible system of linear inequalities in ℝ we give an efficient implementation of this method with complexity polynomial in the number of inequalities and the number of committee elements, but exponential in the dimension of the space. For this implementation, we give experimental results for n = 2, 3. [ABSTRACT FROM AUTHOR]

Abstract: We present a method for finding optimal controlled variables, which are polynomial combinations of measurements. Controlling these variables gives optimal steady state operation. Our work extends the concept of self-optimizing control; starting from the first-order necessary optimality conditions, any unknown variables are eliminated using elimination theory for polynomial systems to obtain invariant variable combinations, which contain only known variables (measurements). If a disturbance causes the active constraints to change, the invariants may be used to identify, and switch to the right region. This makes the method applicable over a wide disturbance range with changing active sets. The procedure is applied to two case studies of continuous stirred tank reactors. [Copyright &y& Elsevier]

In this paper we define a new type of connexive logics which we call Boolean connexive logics. In such logics negation, conjunction and disjunction behave in the classical, Boolean way. We determine these logics through application of the relating semantics. In the final section we present a tableau approach to the discussed logics. [ABSTRACT FROM AUTHOR]

In this study, a new paraconsistent four-valued logic called biclassical connexive logic (BCC) is introduced as a Gentzen-type sequent calculus. Cut-elimination and completeness theorems for BCC are proved, and it is shown to be decidable. Duality property for BCC is demonstrated as its characteristic property. This property does not hold for typical paraconsistent logics with an implication connective. The same results as those for BCC are also obtained for MBCC, a modal extension of BCC. [ABSTRACT FROM AUTHOR]

We present a proof-theoretical analysis of the theory of definite descriptions which emerges from Frege's approach and was formally developed by Kalish and Montague. This theory of definite descriptions is based on the assumption that all descriptions are treated as genuine terms. In particular, a special object is chosen as a designatum for all descriptions which fail to designate a unique object. Kalish and Montague provided a semantical treatment of such theory as well as complete axiomatic and natural deduction formalization. In the paper we provide a sequent calculus formalization of this logic and prove cut elimination theorem in the constructive manner. [ABSTRACT FROM AUTHOR]

This paper describes several parallel algorithmic variations of the Neville elimination. This elimination solves a system of linear equations making zeros in a matrix column by adding to each row an adequate multiple of the preceding one. The parallel algorithms are run and compared on different multi- and many-core platforms using parallel programming techniques as MPI, OpenMP and CUDA. [ABSTRACT FROM AUTHOR]

Abstract: Elimination methods are highly effective for the solution of linear and nonlinear systems of equations, but reversal of the elimination principle can be beneficial as well: competent incorporation of additional independent constraints and variables or more generally immersion of the original computational problem into a larger task, defined by a larger number of independent constraints and variables can improve global convergence of iterative algorithms, that is their convergence from the start. A well known example is the dual linear and nonlinear programming, which enhances the power of optimization algorithms. We believe that this is just an ad hoc application of general Principle of Expansion with Independent Constraints; it should be explored systematically for devising iterative algorithms for the solution of equations and systems of equations and for optimization. At the end of this paper we comment on other applications and extensions of this principle. Presently we show it at work for the approximation of a single zero of a univariate polynomial of a degree . Empirical global convergence of the known algorithms for this task is much weaker than that of the algorithms for all zeros, such as Weierstrass–Durand–Kerner’s root-finder, which reduces its root-finding task to Viète’s (Vieta’s) system of polynomial equations with unknowns. We adjust this root-finder to the approximation of a single zero of , preserve its fast global convergence and decrease the number of arithmetic operations per iteration from quadratic to linear. Together with computing a zero of a polynomial , the algorithm deflates this polynomial as by-product, and then could be reapplied to the quotient to approximate the next zero of . Alternatively by using processors that exchange no data, one can concurrently approximate up to zeros of . Our tests confirm the efficiency of the proposed algorithms. Technically our root-finding boils down to computations with structured matrices, polynomials and partial fraction decompositions. Our study of these links can be of independent interest; e.g., as by-product we express the inverse of a Sylvester matrix via its last column, thus extending the celebrated result of Gohberg and Sementsul (1972) from Toeplitz to Sylvester matrix inverses. [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: Newton, in notes that he would rather not have seen published, described a process for solving simultaneous equations that later authors applied specifically to linear equations. This method — which Euler did not recommend, which Legendre called “ordinary,” and which Gauss called “common” — is now named after Gauss: “Gaussian” elimination. Gauss’s name became associated with elimination through the adoption, by professional computers, of a specialized notation that Gauss devised for his own least-squares calculations. The notation allowed elimination to be viewed as a sequence of arithmetic operations that were repeatedly optimized for hand computing and eventually were described by matrices. [Copyright &y& Elsevier]

Abstract: Neville elimination is a direct method for solving linear systems. Several pivoting strategies for Neville elimination, including pairwise pivoting, are analyzed. Bounds for two different kinds of growth factors are provided. Finally, an approximation of the average normalized growth factor associated with several pivoting strategies is computed and analyzed using random matrices. [ABSTRACT FROM AUTHOR]

As the only nonlinear operation, masked S-box is the core to resist differential power attack (DPA) for advanced encryption standard (AES) cipher chips. In order to suit for the resource-constrained applications, a compact masked S-box based on composite field is proposed in this paper. Firstly, the architecture of masked S-box is designed with composite field masking method. Secondly, four masked S-boxes based on GF ((24)2), which are based on four basis methods with the optimal coefficient and the corresponding optimal root, are implemented and optimized by the delay-aware common subexpression elimination (DACSE) algorithm. Finally, experimental results show that, while maintaining the DPA-resistance performance, our best masked S-box achieves better area performance with the fastest speed compared with the existing works. Therefore, our masked S-box is suitable for resource-constrained applications with fast speed requirements. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we present some results showing the good behavior of the τ-invariant of a Rees algebra with integral closure and elimination (of variables). [ABSTRACT FROM AUTHOR]

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: An important property of chordal graphs is that these graphs are characterized by the existence of perfect elimination orderings on their vertex sets. In this paper, we generalize the notion of perfect elimination orderings to signed graphs, and give a characterization for graphs admitting such orderings, together with characterizations restricted to some subclasses and further properties of those graphs. The definition of our generalized perfect elimination orderings is motivated by a generalization of the classical result that a so-called graphic hyperplane arrangement is free if and only if the corresponding graph is chordal. [Copyright &y& Elsevier]

Abstract: We develop in this paper methods for studying the implicitization problem for a rational map defining a hypersurface in , based on computing the determinant of a graded strand of a Koszul complex. We show that the classical study of Macaulay resultants and Koszul complexes coincides, in this case, with the approach of approximation complexes and we study and give a geometric interpretation for the acyclicity conditions. Under suitable hypotheses, these techniques enable us to obtain the implicit equation, up to a power, and up to some extra factor. We give algebraic and geometric conditions for determining when the computed equation defines the scheme theoretic image of ϕ, and, what are the extra varieties that appear. We also give some applications to the problem of computing sparse discriminants. [Copyright &y& Elsevier]

Roger Crisp distinguishes a positive and a negative aspect of the buck-passing account of goodness (BPA), and argues that the positive account should be dropped in order to avoid certain problems, in particular, that it implies eliminativism about value. This eliminativism involves what I call an ontological claim, the claim that there is no real property of goodness, and an error theory, the claim that all value talk is false. I argue first that the positive aspect of the BPA is necessary to explain the negative aspect. I accept the ontological claim but argue that this does not imply any sort of error theory about value. [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: Elimination Game is a well-known algorithm that simulates Gaussian elimination of matrices on graphs, and it computes a triangulation of the input graph. The number of fill edges in the computed triangulation is highly dependent on the order in which Elimination Game processes the vertices, and in general the produced triangulations are neither minimum nor minimal. In order to obtain a triangulation which is close to minimum, the Minimum Degree heuristic is widely used in practice, but until now little was known on the theoretical mechanisms involved. In this paper we show some interesting properties of Elimination Game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. This results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from Elimination Game. One of the strengths of the new approach is that it is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. In addition, the insight that we gain through Elimination Game is used to partly explain the good behavior of the Minimum Degree algorithm. We also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent. [Copyright &y& Elsevier]

This paper proposes a robust and accurate method for measuring 3-D surfaces using a binocular system. To eliminate the effect caused by the distortion of projector lens, each structured light sheet is fitted to a conicoid. A curvilinear detector, which combines the zero-crossing detection algorithm with Steger's detector, is employed to detect the sub pixel locations of the light stripes, thus preventing the Steger's curvilinear detector from failing to detect them in the end points of the stripes. The proposed coding method combines the information of the linked line with the gray code to avoid producing outliers caused by erroneous decoding and make the coding procedure more robust. Experiments showed that each structured light sheet fitted to a conicoid can effectively improve the measurement accuracy. The subpixel detection method can detect the exact sub pixel locations of the stripes. Likewise, the encoding strategy results in the production of fewer outliers, while the reconstruction result becomes more perfect. [ABSTRACT FROM AUTHOR]

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]

The article focuses on the elimination of political gerrymandering by fair majority voting (FMV). Political gerrymandering is a practice of dividing geographical area into electoral districts to give one political party an unfair advantage by stretching the opposition's voting strength. It is stated that computer technology advancements have permitted a great leap forward of political gerrymandering. FMV is presented as the answer to political gerrymandering. In FMV, voters cast ballots in single-member districts but in voting for a candidate, each gives a vote to the candidate's party. The rules deciding the candidates to be elected is calculated by Jefferson's method of apportionment on the basis of total party votes and the candidates elected are determined through dual approach.

Summary: During development, the formation of mature neural circuits requires the selective elimination of inappropriate synaptic connections. Here we show that C1q, the initiating protein in the classical complement cascade, is expressed by postnatal neurons in response to immature astrocytes and is localized to synapses throughout the postnatal CNS and retina. Mice deficient in complement protein C1q or the downstream complement protein C3 exhibit large sustained defects in CNS synapse elimination, as shown by the failure of anatomical refinement of retinogeniculate connections and the retention of excess retinal innervation by lateral geniculate neurons. Neuronal C1q is normally downregulated in the adult CNS; however, in a mouse model of glaucoma, C1q becomes upregulated and synaptically relocalized in the adult retina early in the disease. These findings support a model in which unwanted synapses are tagged by complement for elimination and suggest that complement-mediated synapse elimination may become aberrantly reactivated in neurodegenerative disease. [Copyright &y& Elsevier]

Summary: The OspF family of phosphothreonine lyase, including SpvC from Salmonella, irreversibly inactivates the dual-phosphorylated host MAPKs (pT-X-pY) through β elimination. We determined crystal structures of SpvC and its complex with a phosphopeptide substrate. SpvC adopts a unique fold of α/β type. The disordered N terminus harbors a canonical D motif for MAPK substrate docking. The enzyme-substrate complex structure indicates that recognition of the phosphotyrosine followed by insertion of the threonine phosphate into an arginine pocket places the phosphothreonine into the enzyme active site. This requires the conformational flexibility of pT-X-pY, which suggests that p38 (pT-G-pY) is likely the preferred physiological substrate. Structure-based biochemical and enzymatic analysis allows us to propose a general acid/base mechanism for β elimination reaction catalyzed by the phosphothreonine lyase. The mechanism described here provides a structural understanding of MAPK inactivation by a family of pathogenic effectors conserved in plant and animal systems and may also open a new route for biological catalysis. [Copyright &y& Elsevier]

Item test analysis is an aid to identify items that need to be eliminated from an assessment. An automatic elimination procedure based on item statistics, therefore, could help to increase the quality of a test in an objective manner. This was investigated by studying the effect of a standardized elimination procedure on the test results of a second-year course over a period of 6 successive years in 1,624 candidates. Cohort effects on the item elimination were examined by determining the number of additional items that had to be eliminated from three different tests in 3 successive academic years in two cohorts. The items that were part of more than one test and had to be eliminated according to the procedure in at least one of the tests appeared to have to be retained according to the same procedure in most of the other tests. The procedure harmed the high scoring students relatively more often than the other students, and the number of eliminated items appeared to be cohort dependent. As a consequence, automatic elimination procedures obscure the transparency of the grading process unacceptably and transform valid tests into inadequate samples of the course content. [ABSTRACT FROM AUTHOR]

Hyperthermal collisions of ground-state atomic oxygen with H2O have been investigated, with special attention paid to the H-atom elimination reaction, O(3P) H2O(X 1A1) → HO2(2A‘) H(2S). This reaction was observed in a crossed-beams experiment, and the relative excitation function in the region around its energy threshold (50−80 kcal mol-1) was measured. Direct dynamics calculations were also performed at two levels of theory, B3LYP/6-31G(d,p) and MP2/6-31G(d,p). The shape of the B3LYP excitation function closely matches that of the experiment. The calculations provided a detailed description of the dynamics and revealed a striking dependence of the reaction mechanism on collision energy, where the cross section rises from a threshold near 60 kcal mol-1to a peak at ∼115 kcal mol-1and then decreases at higher energies as secondary dissociation of the internally excited HO2product becomes dominant. The calculations show that the cross section for H-atom elimination (O H2O → HO2H) is about 10−25% that of the H-atom abstraction (O H2O → OH OH) cross section for collision energies in the 70−160 kcal mol-1range. [ABSTRACT FROM AUTHOR]

The results are reported of mass-spectrometric studies of the nucleobases adenine 1h (1, R = H), guanine 2h, and cytosine 3h. The protonated nucleobases are generated by electrospray ionization of adenosine 1r (1, R = ribose), guanosine 2r, and deoxycytidine 3d (3, R = deoxyribose) and their fragmentations were studied with tandem mass spectrometry. In contrast to previous EI-MS studies of the nucleobases, NH3 elimination does present a major path for the fragmentations of the ions [1h + H]+, [2h + H]+, and [3h + H]+. The ion [2h + H − NH3]+ also was generated from the acyclic precursor 5-cyanoamino-4-oxomethylene-dihydroimidazole 13h and from the thioether derivative 14h of 2h (NH2 replaced by MeS). The analyses of the modes of initial fragmentation is supported by density functional theoretical studies. Conjugate acids 15–55 were studied to determine site preferences for the protonations of 1h, 2h, 3h, 13h, and 14h. The proton affinity of the amino group hardly ever is the substrate’s best protonation site, and possible mechanisms for NH3 elimination are discussed in which the amino group serves as the dissociative protonation site. The results provide semi-direct experimental evidence for the existence of the pyrimidine ring-opened cations that we had proposed on the basis of theoretical studies as intermediates in nitrosative nucleobase deamination. [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]

In the context of multiple constant multiplications (MCM) design, we propose a novel common-subexpression-elimination (CSE) algorithm that models synthesis of coefficients into an estimated cost function. Although the proposed algorithm generally does not guarantee an optimum solution, it is capable of finding the minimum/minima of the function in practically sized problems. In our design examples that have known optimal solutions, syntheses of coefficients using the proposed method match the optimal results in a defined search space. We also discover the relationhsip and propose an improvement search space for optimization that combine all minimal-signed-digit (MSD) representations as well as the shifted sum (difference) of coefficients to explore the hidden relationship. In some cases, the proposed feasible solution space further reduces the number of adders/subtractors in the synthesis of MCM from all MSD representations. [ABSTRACT FROM AUTHOR]

Abstract: Elimination is a classical subject. The problem is algorithmically solvable by using resultants or by one calculation of Groebner basis with respect to an elimination term order. However, there is no existing method that is both efficient and reliable enough for applicable size problems, say implicitization of bi-cubic Bezier surfaces with degree six in five variables. This basic and useful operation in computer aided geometric design and geometric modeling defies a solution even when approximation using floating-point or modular coefficients is used for Groebner basis computation. An elimination term order can be used to eliminate for any ideal in . However, for most practical problems we are given a fixed ideal, which means that an elimination term order may be too much for our calculation. In this paper, the author proposes a new approach for elimination. Instead of using a classical elimination term order for all problems or ideals as usual, the author proposes to use algebraic structures of the given system of equations for finding more suitable term orders for elimination of the given problem only. Experimental results showed that these ideal-specific term orders are much more efficient for elimination. In particular, when ideal specific term orders for elimination are used with Groebner walk conversion, one can completely avoid all perturbations. This is a significant result because researchers have been struggling with how to perturb basis conversions for a long time. [Copyright &y& Elsevier]

Abstract: A pivoting strategy of operations for the Neville elimination of n × n nonsingular sign regular matrices is introduced. Among other nice properties, it is proved that it preserves sign regularity. It is also shown its relationship with scaled partial pivoting strategies for Neville elimination. [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]