The Termination Hierarchy for Term Rewriting

A number of properties of term rewriting systems related to termination are discussed. It is examined how these properties are affected by modifications in the definitions like weakening the requirement of strict monotonicity and adding embedding rules. All counterexamples to prove non-equivalence of properties are string rewriting systems, in most cases even single string rewrite rules. Received: June 15, 1999; revised version: August 7, 2000     

Adding constants to string rewriting

We consider unary term rewriting, i.e., term rewriting with unary signatures where all function symbols are either unary or constants. Terms over such signatures can be transformed into strings by just reading all symbols in the term from left to right, ignoring the optional variable. By lifting this transformation to rewrite rules, any unary term rewrite system (TRS) is transformed into a corresponding string rewrite system (SRS). We investigate which properties are preserved by this transformation. It turns out that any TRS over a unary signature is terminating if and only if the corresponding SRS is terminating. In this way tools for proving termination of string rewriting can be applied for proving termination of unary TRSs. For other rewriting properties including confluence, unique normal form property, weak normalization and relative termination, we show that a similar corresponding preservation property does not hold. Supported by the Deutsche Forschungsgemeinschaft DFG under grant GI 274/5-1. This research was done while the first author was at the LuFG Informatik 2, RWTH Aachen.     

Investigation of integration algorithms for rate-dependent crystal plasticity using explicit finite element codes

The work presented here concerns the use of rate-dependent crystal plasticity into explicit dynamic finite element codes for structural analysis. Different integration or stress update algorithms for the numerical implementation of crystal plasticity, two explicit algorithms and a fully-implicit one, are described in detail and compared in terms of convergence, accuracy and computation time. The results show that the implicit time integration is very robust and stable, provided low enough convergence tolerance is used for low strain-rate sensitivity coefficients, while being the slowest in terms of CPU time. Explicit methods prove to be fast, stable and accurate. The algorithms are then applied to two structural analyses, one concerning flat rolling of a polycrystalline slab and another on the response of a multicrystalline sample under uniaxial tensile condition. The results show that the explicit algorithms perform well with simulation times much smaller compared to their implicit counterpart. Finally, mesh sensitivity for the second structural analysis is investigated and shows to slightly affect the global response of the structure.     

Undecidable properties of flat term rewrite systems

Reachability, joinability and confluence properties are known to be undecidable for flat term rewrite systems (TRS). We give shorter and conceptually simpler proofs of these results. We also prove undecidability of weak normalization and unique normalization properties for flat TRS. The first author was supported by Spanish Ministry of Education and Science by the FORMALISM project (TIN2007-66523) and by the LOGICTOOLS-2 project (TIN2007-68093-C02-01). The second author was supported by Spanish Ministry of Education and Science by the FORMALISM project (TIN2007-66523).     

The size-change principle and dependency pairs for termination of term rewriting

In [24], a new size-change principle was proposed to verify termination of functional programs automatically. We extend this principle in order to prove termination and innermost termination of arbitrary term rewrite systems (TRSs). Moreover, we compare this approach with existing techniques for termination analysis of TRSs (such as recursive path orders or dependency pairs). It turns out that the size-change principle on its own fails for many examples that can be handled by standard techniques for rewriting, but there are also TRSs where it succeeds whereas existing rewriting techniques fail. Moreover, we also compare the complexity of the respective methods. To this end, we develop the first complexity analysis for the dependency pair approach. While the size-change principle is PSPACE-complete, we prove that the dependency pair approach (in combination with classical path orders) is only -complete. To benefit from their respective advantages, we show how to combine the size-change principle with classical orders and with dependency pairs. In this way, we obtain a new approach for automated termination proofs of TRSs which is more powerful than previous approaches. We also show that the combination with dependency pairs does not increase the complexity of the size-change principle, i.e., the combined approach is still PSPACE-complete.     

Comparative study of numerical explicit schemes for impact problems

Explicit numerical schemes are used to integrate in time finite element discretization methods. Unfortunately, these numerical approaches can induce high-frequency numerical oscillations into the solution. To eliminate or to reduce these oscillations, numerical dissipation can be introduced. The paper deals with the comparison of three different explicit schemes: the central-difference scheme which is a non-dissipative method, the Hulbert-Chung dissipative explicit scheme and the Tchamwa-Wielgosz dissipative scheme. Particular attention is paid to the study of these algorithms' behavior in problems involving high-velocity impacts like Taylor anvil impact and bullet-target interactions. It is shown that Tchamwa-Wielgosz scheme is efficient in filtering the high-frequency oscillations and is more dissipative than Hulbert-Chung explicit scheme. Although its convergence rate is only first order, the loss of accuracy remains limited to acceptable values.     

On the relative power of polynomials with real, rational, and integer coefficients in proofs of termination of rewriting

In the seventies, Manna and Ness, Lankford, and Dershowitz pionneered the use of polynomial interpretations with integer and real coefficients in proofs of termination of rewriting. More than twenty five years after these works were published, however, the absence of true examples in the literature has given rise to some doubts about the possible benefits of using polynomials with real or rational coefficients. In this paper we prove that there are, in fact, rewriting systems that can be proved polynomially terminating by using polynomial interpretations with (algebraic) real coefficients; however, the proof cannot be achieved if polynomials only contain rational coefficients. We prove a similar statement with respect to the use of rational coefficients versus integer coefficients. Tel.: +34 96 387 7007 (ext. 73531)     

Generalized sufficient conditions for modular termination of rewriting

Modular properties of term rewriting systems, i.e. properties which are preserved under disjoint unions, have attracted an increasing attention within the last few years. Whereas confluence is modular this does not hold true in general for termination. By means of a careful analysis of potential counterexamples we prove the following abstract result. Whenever the disjoint union _{1 2} of two (finitely branching) terminating term rewriting systems ₁, ₂ is non-terminating, then one of the systems, say ₁, enjoys an interesting (undecidable) property, namely it is not termination preserving under non-deterministic collapses, i.e. ₁ {itG(x, y) x, G(x, y) y} is non-terminating, and the other system ₂ is collapsing, i.e. contains a rule with a variable right hand side. This result generalizes known sufficient criteria for modular termination of rewriting and provides the basis for a couple of derived modularity results. Furthermore, we prove that the minimal rank of potential counterexamples in disjoint unions may be arbitrarily high which shows that interaction of systems in such disjoint unions may be very subtle. Finally, extensions and generalizations of our main results in various directions are discussed. In particular, we show how to generalize the main results to some restricted form of non-disjoint combinations of term rewriting systems, namely for combined systems with shared constructors.This research was supported by the Deutsche Forschungsgemeinschaft, SFB 314 (D4-Projekt).     

An Improved General Path Order

We define a strong and versatile termination order for term rewriting systems, called theImproved General Path Order, which simplifies and strengthens Dershowitz/Hoot's General Path Order. We demonstrate the power of the Improved General Path Order by proofs of termination of non-trivial examples, among them a medium-scale term rewriting system that models a lift control.     

Simple termination is difficult

A terminating term rewriting system is called simply terminating if its termination can be shown by means of a simplification ordering, an ordering with the property that a term is always bigger than its proper subterms. Almost all methods for proving termination yield, when applicable, simple termination. We show that simple termination is an undecidable property, even for one-rule systems. This contradicts a result by Jouannaud and Kirchner. The proof is based on the ingenious construction of Dauchet who showed the undecidability of termination for one-rule systems. Our results may be summarized as follows: being simply terminating, (non-)self-embedding, and (non-)looping are undecidable properties of orthogonal, variable preserving, one-rule constructor systems.A preliminary version of this paper appeared in the Proceedings of the 5th International Conference on Rewriting Techniques and Applications, Montreal, Lecture Notes in Computer Science 690, pp. 228–242, 1993.     

Completeness results for basic narrowing

In this paper we analyze completeness results for basic narrowing. We show that basic narrowing is not complete with respect to normalizable solutions for equational theories defined by confluent term rewriting systems, contrary to what has been conjectured. By imposing syntactic restrictions on the rewrite rules we recover completeness. We refute a result of Hölldobler which states the completeness of basic conditional narrowing for complete (i.e. confluent and terminating) conditional term rewriting systems without extra variables in the conditions of the rewrite rules. In the last part of the paper we extend the completeness results of Giovannetti and Moiso for level-confluent and terminating conditional systems with extra variables in the conditions to systems that may also have extra variables in the right-hand sides of the rules.An extended abstract of this paper appeared asCounterexamples to Completeness Results for Basic Narrowing (Extended Abstract) in the Proceedings of the 3rd International Conference on Algebraic and Logic Programming, Volterra, Lecture Notes in Computer Sciences 632, pp. 244–258, 1992. Most of the work reported in this paper was carried out while the first author was employed at the Department of Software Technology, CWI, Kruislaan 413, 1098 SJ Amsterdam, and the second author at the Department of Mathematics and Computer Science, Vrije Universiteit, de Boelelaan 1081a, 1081 HV Amsterdam.Partially supported by ESPRIT Basic Research Action 3020, INTEGRATION.     

Stability analysis of an explicit finite element scheme for plane wave motions in elastic solids

 Expressions for critical timesteps are provided for an explicit finite element method for plane elastodynamic problems in isotropic, linear elastic solids. Both 4-node and 8-node quadrilateral elements are considered. The method involves solving for the eigenvalues directly from the eigenvalue problem at the element level. The characteristic polynomial is of order 8 for 4-node elements and 16 for 8-node elements. Due to the complexity of these equations, direct solution of these polynomials had not been attempted previously. The commonly used critical time-step estimates in the literature were obtained by reducing the characteristic equation for 4-node elements to a second-order equation involving only the normal strain modes of deformation. Furthermore, the results appear to be valid only for lumped-mass 4-node elements. In this paper, the characteristic equations are solved directly for the eigenvalues using <ty>Mathematica<ty> and critical time-step estimates are provided for both lumped and consistent mass matrix formulations. For lumped-mass method, both full and reduced integration are considered. In each case, the natural modes of deformation are obtained and it is shown that when Poisson's ratio is below a certain transition value, either shear-mode or hourglass mode of deformation dominates depending on the formulation. And when Poisson's ratio is above the transition value, in all the cases, the uniform normal strain mode dominates. Consequently, depending on Poisson's ratio the critical time-step also assumes two different expressions. The approach used in this work also has a definite pedagogical merit as the same approach is used in obtaining time-step estimates for simpler problems such as rod and beam elements. Received: 8 January 2002 / Accepted: 12 July 2002 The support of NSF under grant number DMI-9820880 is gratefully acknowledged.     

Refutational theorem proving for hierarchic first-order theories

We extend previous results on theorem proving for first-order clauses with equality to hierarchic first-order theories. Semantically such theories are confined to conservative extensions of the base models. It is shown that superposition together with variable abstraction and constraint refutation is refutationally complete for theories that are sufficiently complete with respect to simple instances. For the proof we introduce a concept of approximation between theorem proving systems, which makes it possible to reduce the problem to the known case of (flat) first-order theories. These results allow the modular combination of a superposition-based theorem prover with an arbitrary refutational prover for the primitive base theory, whose axiomatic representation in some logic may remain hidden. Furthermore they can be used to eliminate existentially quantified predicate symbols from certain second-order formulae.     

A Complete Characterization of Termination of 0p 1q→ 1r 0s

We characterize termination of one-rule string rewriting systems of the form 0 ^p 1 ^q → 1 ^r 0 ^s for every choice of positive integers p, q, r, and s. In doing so we introduce a termination proof method that applies to some hard examples. For the simply terminating cases, i.e. string rewriting systems that can be ordered by a division order, we give the precise complexity of derivation lengths. Received: July 31, 1997; revised version: January 30, 2000     

Significance of knowledge sources for a text-to-speech system for Indian languages

This paper discusses the significance of segmental and prosodic knowledge sources for developing a text-to-speech system for Indian languages. Acoustic parameters such as linear prediction coefficients, formants, pitch and gain are prestored for the basic speech sound units corresponding to the orthographic characters of Hindi. The parameters are concatenated based on the input text. These parameters are modified by stored knowledge sources corresponding to coarticulation, duration and intonation. The coarticulation rules specify the pattern of joining the basic units. The duration rules modify the inherent duration of the basic units based on the linguistic context in which the units occur. The intonation rules specify the overall pitch contour for the utterance (declination or rising contour), fall-rise patterns, resetting phenomena and inherent fundamental frequency of vowels. Appropriate pauses between syntactic units are specified to enhance intelligibility and naturalness.     

Some explicit expressions for the probability distribution of force magnitude

Recently, empirical investigations have suggested that the components of contact forces follow the exponential distribution. However, explicit expressions for the probability distribution of the corresponding force magnitude have not been known and only approximations have been used in the literature. In this note, for the first time, I provide explicit expressions for the probability distribution of the force magnitude. Both two-dimensional and three-dimensional cases are considered.     

Modelling of safety glass for crash simulation

In this paper, we present a numerical technique to simulate the crash behaviour of laminated safety glass via finite elements. As the main aspect of this work, we consider two coincided elements: a shell element for glass and a membrane element for the hyperelastic PVB-interlayer. We give an overview of hyperelastic models, which are used in crash simulations and investigate the material laws by Blatz–Ko, Mooney–Rivlin and Ogden. The obtained stress–strain curves are fitted by experimental results of the interlayer. For a comparison, we use an one-material-model with piecewise linear plasticity and a laminated glass model assigning material properties to the integration points. As practical applications, we simulate an impact of a sphere into a glass plate and investigate the behaviour of a windscreen during a roof crash.     

An alternative explicit formulation for the DKT plate-bending element

The stiffness matrix for the DKT plate-bending element is formulated explicitly in a global co-ordinate system. This approach avoids transformations of stiffness, and elasticity properties for anisotropic materials, from local to global co-ordinates, which were required in previous formulations. A FORTRAN listing of the algorithm is appended for potential users.