Springer Science and Business Media LLC

A fast algorithm is given to produce a small set of short sentences from a context free grammar such that each production of the grammar is used at least once. The sentences are useful for testing parsing programs and for debugging grammars (finding errors in a grammar which causes it to specify some language other than the one intended). Some experimental results from using the sentences to test some automatically generated simpleLR(1) parsers are also given.

In this paper, we show that if a lower-order Hankel tensor is positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS), then its associated higher-order Hankel tensor with the same generating vector, where the higher order is a multiple of the lower order, is also positive semi-definite (or positive definite, or negative semi-definite, or negative definite, or SOS, respectively). Furthermore, in this case, the extremal H-eigenvalues of the higher order tensor are bounded by the extremal H-eigenvalues of the lower order tensor, multiplied with some constants. Based on this inheritance property, we give a concrete sum-of-squares decomposition for each strong Hankel tensor. Then we prove the second inheritance property of Hankel tensors, i.e., a Hankel tensor has no negative (or non-positive, or positive, or nonnegative) H-eigenvalues if the associated Hankel matrix of that Hankel tensor has no negative (or non-positive, or positive, or nonnegative, respectively) eigenvalues. In this case, the extremal H-eigenvalues of the Hankel tensor are also bounded by the extremal eigenvalues of the associated Hankel matrix, multiplied with some constants. The third inheritance property of Hankel tensors is raised as a conjecture.

The characterization ofA-stable methods is often considered as a very difficult task (see e.g. [1]). In recent years, simple proofs have been found for methods of orderp≧2m-2 (see [2], [3], [7]). In this paper, we characterize theA-acceptable approximations of orderp ≧2m-4 and apply the result to 12-parameter families of implicit Runge-Kutta methods.

To solve ODE systems with different time scales which are localized over the components, multirate time stepping is examined. In this paper we introduce a self-adjusting multirate time stepping strategy, in which the step size for a particular component is determined by its own local temporal variation, instead of using a single step size for the whole system. We primarily consider implicit time stepping methods, suitable for stiff or mildly stiff ODEs. Numerical results with our multirate strategy are presented for several test problems. Comparisons with the corresponding single-rate schemes show that substantial gains in computational work and CPU times can be obtained.

A class of finite difference schemes for the solution of a nonlinear system of first order differential equations with two point boundary conditions which shares properties with Runge-Kutta processes and gap schemes is discussed. The order conditions for the coefficients of these processes, techniques for reducing these order conditions in number and the symmetry conditions are given. A symmetricA-stable eight order process which has second, fourth and sixth orderA-stable processes embedded in it is given as an example.

The Lebesgue constant is a measure for the stability of the Lagrange interpolation. The decomposition of the Lagrange interpolation operator in their even and odd parts with respect to the last variable can be used to find a relation between the Lebesgue constant for a space of polynomials and the corresponding Lebesgue constants for subspaces of even and odd polynomials. It is shown that such a decomposition preserves the stability properties of the Lagrange interpolation operator. We use the Lebesgue functions to provide pointwise quantitative measures of the stability properties and illustrate with examples the behaviour in simple cases.

Let $$\mathbf{u}$$ denote the relative rounding error of some floating-point format. Recently it has been shown that for a number of standard Wilkinson-type bounds the typical factors $$\gamma _k:=k\mathbf{u}/(1-k\mathbf{u})$$ can be improved into $$k\mathbf{u}$$ , and that the bounds are valid without restriction on $$k$$ . Problems include summation, dot products and thus matrix multiplication, residual bounds for $$LU$$ - and Cholesky-decomposition, and triangular system solving by substitution. In this note we show a similar result for the product $$\prod _{i=0}^k{x_i}$$ of real and/or floating-point numbers $$x_i$$ , for computation in any order, and for any base $$\beta \geqslant 2$$ . The derived error bounds are valid under a mandatory restriction of $$k$$ . Moreover, we prove a similar bound for Horner’s polynomial evaluation scheme.