On quasi-interpretations of grammar forms

The notions of a grammar form and its interpretations were introduced to describe families of structurally related grammars. Basically, a grammar formG is a (context-free) grammar serving as a master grammar and the interpretation operator defines a family of grammars, each structurally related toG. In this paper, a new operator yielding a family of grammars, is introduced as a variant of . There are two major results. The first is that and commute. The second is that for each grammar formG, the collection of all families of grammars ,G′ in , is finite. Expressed otherwise, the second result is that for each grammar formG there is only a bounded number of grammar forms in (G) no two of which are strongly equivalent.     

On the approximate solution of first-kind integral equations of Volterra type

The present paper deals with the approximate solution of integral equations of the first kind, ( y)x∈I:=[a, b], where denotes a (linear) integral operator of Volterra (or Abel) type, and whereg∈C(I), withg(a)=0. The given functiong is approximated uniformly onI (or on a finite subsetZ?I by using certain weak Chebyshev systems onI which are obtained in a natural way. By the linearity of this yields an approximation to the exact solutiony onI. Questions of uniqueness and characterization of such approximating functions, as well as numerical aspects of the approximation problem are discussed.     

Enclosing the solution set of linear systems with inaccurate data by iterative methods based on incomplete LU-decompositions

We present a class of iterative methods to enclose the solution set by an interval vector;A is varying in ann×n intervalH-Matrix andb is varying in an interval vector . The algorithm taken into consideration generalizes an iterative method of Meijerink/van der Vorst based on an incompleteLU-decomposition of anM-MatrixA. Theorems concerning the feasibility of the algorithm, its rate of convergence and its quality of enclosure are given. Since the original method of Meijerink/van der Vorst is a special case of our algorithm we have thus shown its applicability to the larger class ofH-matrices. Furthermore we relate theR ₁-factor (as defined in Ortega/Rheinboldt [9]) of the original method to the underlying setP of indices.     

Generalized symmetric Runge-Kutta methods

In this paper the concept of symmetry for Runge-Kutta methods is generalized to include composite methods. The extrapolations of the usual compositions of a symmetric method ? of the form are shown not to beA-stable. However, this limitation can be overcome by considering composite methods of the form where represents a non-symmetric and possiblyL-stable method called a symmetrizer satisfying . While no longer symmetric, these composite methods yet satisfy and thus share with symmetric methods the important property of admitting asymptotic error expansions in even powers of 1/n. Composite methods that are constructed in this way and presented in this paper have implementation costs comparable to that for the symmetric method. They generalize those based on the implicit midpoint and trapezoidal rules used with the standard smoothing formulae and thus extend the class of methods for acceleration techniques of extrapolation and defect correction. A characterization ofL-stable symmetrizers for 2-stage symmetric methods is given and studied for a particular stiff model problem. The analysis suggests that certainL-stable symmetrizers can play an important role in suppressing order defect effects for stiff problems.     

Complex sector arithmetic

In the past interval analysis in the complex plane has used nearly exclusively the rectangular arithmeticR? resp. the circular arithmeticK?. Both arithmetics satisfy the inclusion property where the equality does not hold in general. To introduce new interval arithmetics it is therefore interesting to consider other subsets of the powerset of?. This paper describes different alternatives of sector arithmetics, for which the equality in (*) is valid.     

On the convergence of some quadrature rules for Cauchy principal-value and finite-part integrals

In this paper sufficient conditions are derived to ensure the convergence of the Elliott and Hunter types of quadrature rules for the evaluation of weighted Cauchy principal-value integrals of the form: The simultaneous convergence in the interval (?1, 1) of both quadratures was established for a class of Hölder-continuous functionsf(f∈H _μ ). Corrections of some previous statements on the subject of convergence of such quadratures are also included. Moreover, a simple derivation of the Hunter and Elliott types of quadrature rules for the evaluation of the derivative of thep-th-order of the abovestated integral was given and sufficient conditions for the convergence of the Hunter-type quadrature were obtained. Thus, the convergence of this integral was ensured for functionsf such thatf ^(p) ∈H _μ .     

Preliminary application of the computer technique to GuQin music research

GuQin(古琴literally,ancient Qin) is one of the oldest Chinese musical instruments.GuQin has its own special way of making notations.Existing GuQin notations incorporate a valuable heritage of Chinese traditional music.Using computers to store GuQin notations and recover the same to typesetting and printing is briefly described in this paper.The prospective applicatiion of computer technique to Chinese traditional music is also discussed.     

Moment inequalities for random variables in computational geometry

LetX ₁,...,X _n be independent identically distributedR ^d -valued random vectors, and letA _n =A(X ₁,...,X _n ) be a subset of {X ₁,...,X _n }, invariant under permutations of the data, and possessing the inclusion property (X ₁ ∈A _n impliesX ₁ ∈A _i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these conditions. LetN _n be the cardinality ofA _n . We show that for allp≥1, there exists a universal constantC _p >0 such thatE(N _n ^p )≤C _p max (1,E ^p ) where . This complements Jensen's lower bound for thep-th moment:E(N _n ^p )≥E ^p (N _n ). The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N _n ) for linear expected time behaviour of divide-and-conquer methods for findingA _n .     

How many minimal upper bounds of minimal upper bounds

We construct a family such that the maximal elementX _n ∈ ? _n can be obtained inductively by computing minimal upper bounds over already generated setsG, involving not less than exponentially many (with respect to |X _n |) such intermediate setsG, starting with minimal ones in ? _n .     

Linearity and iterator types for Gödel’s System

System Open image in new window is a linear λ-calculus with numbers and an iterator, which, although imposing linearity restrictions on terms, has all the computational power of Gödel’s System  Open image in new window . System Open image in new window owes its power to two features: the use of a closed reduction strategy (which permits the construction of an iterator on an open function, but only iterates the function after it becomes closed), and the use of a liberal typing rule for iterators based on iterative types. In this paper, we study these new types, and show how they relate to intersection types. We also give a sound and complete type reconstruction algorithm for System  Open image in new window .     

Ableitungsfreie Abschätzungen bei trigonometrischer Interpolation und Konjugierten-Bestimmung

Letf be 2 π-periodic,T _v its trigonometric interpolation polynomial, \(\bar f\) and \(\bar T_T \) the conjugates off andT _T, respectively. In this note the maximum norms ‖f-T _T‖, \(\parallel f - \bar T_T \parallel \) ‖f′?T _′‖ and \(\parallel \bar f' - \bar T'_T \parallel \) are estimated by the Fourier coefficients off. Iff is analytic on Φ results by Kress [2], [3] are obtained.     

A methodology for verifying SysML requirements using activity diagrams

Designing complex and critical systems needs a methodology to ensure the correctness of their specifications. Within an overall approach which considers the validation of SysML designs, this paper proposes a methodology for verifying SysML requirements on activity diagrams. The objective is to define a complete process to formalize and verify SysML functional requirements related to activity diagrams. Our contributions lie, first, in the definition of AcTRL (Activity Temporal Requirement Language), a new language for the formalization of functional requirements at SysML level. Second, in the proposed verification methodology which is guided by the Open image in new window verify Open image in new window relationships between SysML requirements and activity diagrams. The verification is enabled by formalizing SysML activities with hierarchical coloured Petri nets (HCPNs) and by automatically translating SysML requirements expressed on AcTRL into temporal logic. Our methodology takes into account the hierarchical structure of SysML activities and their relations with SysML requirements to provide a modular and incremental verification. A case study for a ticket vending machine is presented to illustrate the different steps and the benefits of the proposed methodology.     

Uniformly Convergent Cubic Nonconforming Element For Darcy–Stokes Problem

In this paper we construct a cubic element named DSC33 for the Darcy–Stokes problem of three-dimensional space. The finite element space \({{\varvec{V}}}_{h}\) for velocity is Open image in new window -conforming, i.e., the normal component of a function in \({{\varvec{V}}}_{h}\) is continuous across the element boundaries, meanwhile the tangential component of a function in \({{\varvec{V}}}_{h}\) is averagely continuous across the element boundaries, hence \({{\varvec{V}}}_{h}\) is \({{\varvec{H}}}^{1}\)-average conforming. We prove that this element is uniformly convergent with respect to the perturbation constant \(\varepsilon \) for the Darcy–Stokes problem. In addition, we construct a discrete de Rham complex corresponding to DSC33 element. The finite element spaces in the discrete de Rham complex can be applied to some singular perturbation problems.     

Properties of interval operators

In this paper we give some properties of interval operatorsF which guarantee the convergence of the interval sequence {X _k} defined byX _k+1:=F(X_k)∩X_k to a unique fixed interval \(\hat X\) . This interval \(\hat X\) encloses the “zero-set”X ^* of a function strip \(G(x): = [g(x),\bar g(x)]\) . for some known interval operators we investigate under which assumptions these properties are valid.     

Numerical solutions of AXB = C for mirrorsymmetric matrix X under a specified submatrix constraint

Mirrorsymmetric matrices, which are the iteraction matrices of mirrorsymmetric structures, have important application in studying odd/even-mode decomposition of symmetric multiconductor transmission lines (MTL). In this paper we present an efficient algorithm for minimizing ${\|AXB-C\|}$ where ${\|\cdot\|}$ is the Frobenius norm, ${A\in \mathbb{R}^{m\times n}}$ , ${B\in \mathbb{R}^{n\times s}}$ , ${C\in \mathbb{R}^{m\times s}}$ and ${X\in \mathbb{R}^{n\times n}}$ is mirrorsymmetric with a specified central submatrix [x _ij ] _{r≤i, j≤n-r} . Our algorithm produces a suitable X such that AXB = C in finitely many steps, if such an X exists. We show that the algorithm is stable any case, and we give results of numerical experiments that support this claim.     

Interval methods that are guaranteed to underestimate (and the resulting new justification of Kaucher arithmetic)

One of the main objectives of interval computations is, given the functionf(x ₁, ...,x _n ), andn intervals $\bar x_1 ,...,\bar x_n$ , to compute the range $\bar y = f(\bar x_1 ,...,\bar x_n )$ . Traditional methods of interval arithmetic compute anenclosure $Y \supseteq \bar y$ for the desired interval $\bar y$ , an enclosure that is often an overestimation. It is desirable to know how close this enclosure is to the desired range interval. For that purpose, we develop a new interval formalism that produces not only the enclosure, but also theinner estimate for the desired range $\bar y$ , i.e., an interval y such that $y \subseteq \bar y$ . The formulas for this new method turn out to be similar to the formulas of Kaucher arithmetic. Thus, we get a new justification for Kaucher arithmetic.     

Recursive decomposition and bounds of the lattice of Moore co-families

A collection of sets on a ground set U _n (U _n ?=?{1,2,...,n}) closed under intersection and containing U _n is known as a Moore family. The set of Moore families for a fixed n is in bijection with the set of Moore co-families (union-closed families containing the empty set) denoted $\mathbb{M}_n$ . In this paper, we propose a recursive definition of the set of Moore co-families on U _n . Then we apply this decomposition result to compute a lower bound on $|\mathbb M_n|$ as a function of $|\mathbb M_{n-1}|$ , the Dedekind numbers and the binomial coefficients. These results follow the work carried out in [1] to enumerate the number of Moore families on U ₇.     

Randomness Buys Depth for Approximate Counting

We show that the promise problem of distinguishing n-bit strings of relative Hamming weight \({1/2 + \Omega(1/{\rm lg}^{d-1} n)}\) from strings of weight \({1/2 - \Omega(1/{\rm \lg}^{d - 1} n)}\) can be solved by explicit, randomized (unbounded fan-in) poly(n)-size depth-d circuits with error \({\leq 1/3}\) , but cannot be solved by deterministic poly(n)-size depth-(d+1) circuits, for every \({d \geq 2}\) ; and the depth of both is tight. Our bounds match Ajtai’s simulation of randomized depth-d circuits by deterministic depth-(d + 2) circuits (Ann. Pure Appl. Logic; ’83) and provide an example where randomization buys resources. To rule out deterministic circuits, we combine Håstad’s switching lemma with an earlier depth-3 lower bound by the author (Computational Complexity 2009). To exhibit randomized circuits, we combine recent analyses by Amano (ICALP ’09) and Brody and Verbin (FOCS ’10) with derandomization. To make these circuits explicit, we construct a new, simple pseudorandom generator that fools tests \({A_1 \times A_2 \times \cdots \times A_{{\rm lg}{n}}}\) for \({A_i \subseteq [n], |A_{i}| = n/2}\) with error 1/n and seed length O(lg n), improving on the seed length \({\Omega({\rm lg}\, n\, {\rm lg}\, {\rm lg}\, n)}\) of previous constructions.