Expression Reduction Systems with Patterns

We introduce a new higher-order rewriting formalism, called expression reduction systems with patterns (ERSP), where abstraction is allowed not only on variables but also on nested patterns with metavariables. These patterns are built by combining standard algebraic patterns with choice constructors denoting cases. In other words, the nondeterministic choice between different rewrite rules which is inherent to classical rewriting formalisms can be lifted here to the level of patterns. We show that confluence holds for a reasonable class of systems and terms.     

Graph rewriting systems for the entity-relationship approach

Sequential graph rewriting systems are proposed as a meta-level formalism providing the concise and sound definition of different ER diagram languages. These rewriting systems can be used to define ER-based approaches for various DB modelling subtasks like schema design, evolution and integration. In addition, they are a natural choice for syntax directed ER CASE workbenches. In particular, by using specialized ER graph rewriting systems as meta input for CASE tools, the resulting tool behavior can be guided and controlled. Moreover, grammar driven modelling tools can be easily adapted for the needs of a particular enterprise or software factory without superimposing a particular ER dialect on the end users. Additional benefits result from the use of ER graph rewriting systems as a comparison framework for the continuously enlarging set of ER dialects.

The presentation includes material on the ER graph rewriting formalism, i.e., the actual tool, as well as an introduction to some formal graph rewriting prerequisites. An exemplary application, in particular ER graph generation, is used to clarify the underlying formal concepts.     

Effective strategic programming for Java developers

In object programming languages, the Visitor design pattern allows separation of algorithms and data structures. When applying this pattern to tree‐like structures, programmers are always confronted with the difficulty of making their code evolve. One reason is that the code implementing the algorithm is interwound with the code implementing the traversal inside the visitor. When implementing algorithms such as data analyses or transformations, encoding the traversal directly into the algorithm turns out to be cumbersome as this type of algorithm only focuses on a small part of the data‐structure model (e.g., program optimization). Unfortunately, typed programming languages like Java do not offer simple solutions for expressing generic traversals. Rewrite‐based languages like ELAN or Stratego have introduced the notion of strategies to express both generic traversal and rule application control in a declarative way. Starting from this approach, our goal was to make the notion of strategic programming available in a widely used language such as Java and thus to offer generic traversals in typed Java structures. In this paper, we present the strategy language SL that provides programming support for strategies in Java. Copyright © 2012 John Wiley & Sons, Ltd.     

Categorical models for local names

This paper describes the construction of categorical models for thenu-calculus, a language that combines higher-order functions with dynamically creatednames. Names are created with local scope, they can be compared with each other and passed around through function application, but that is all.The intent behind this language is to examine one aspect of the imperative character of Standard ML: the use of local state by dynamic creation of references. The nu-calculus is equivalent to a certain fragment of ML, omitting side effects, exceptions, datatypes and recursion. Even without all these features, the interaction of name creation with higher-order functions can be complex and subtle; it is particularly difficult to characterise theobservable behaviour of expressions.Categorical monads, in the style of Moggi, are used to build denotational models for the nu-calculus. An intermediate stage is the use of a computational metalanguage, which distinguishes in the type system between values and computations.The general requirements for a categorical model are presented, and two specific examples described in detail. These provide a sound denotational semantics for the nu-calculus, and can be used to reason about observable equivalence in the language. In particular a model using logical relations is fully abstract for first-order expressions.Supported by UK SERC studentship 91307943 and CEC SCIENCE project PL910296     

Computational aspects of the bilinear transformation basedalgorithm for S-plane to Z-plane mapping

The author analyzes the computational complexity of an algorithm by F.D. Groutage et al. (ibid., vol.AC-32, no.7, p.635-7, July 1987) for performing the transformation of a continuous transfer function to a discrete equivalent by a bilinear transformation. Groutage et al. defend their method by noting that their technique is not limited to the bilinear transformation. Rather, it can be extended to any higher-order integration rule (Simpson, Runge-Kutta, etc.), or to any higher-order expansion of the ln function. In general, using the method, s can be any appropriate mapping function s=f (z)     

A kernel optimization method based on the localized kernel Fisher criterion

It is widely recognized that whether the selected kernel matches the data determines the performance of kernel-based methods. Ideally it is expected that the data is linearly separable in the kernel induced feature space, therefore, Fisher linear discriminant criterion can be used as a cost function to optimize the kernel function. However, the data may not be linearly separable even after kernel transformation in many applications, e.g., the data may exist as multimodally distributed structure, in this case, a nonlinear classifier is preferred, and obviously Fisher criterion is not a suitable choice as kernel optimization rule. Motivated by this issue, we propose a localized kernel Fisher criterion, instead of traditional Fisher criterion, as the kernel optimization rule to increase the local margins between embedded classes in kernel induced feature space. Experimental results based on some benchmark data and measured radar high-resolution range profile (HRRP) data show that the classification performance can be improved by using the proposed method.     

Matrix-variate and higher-order probabilistic projections

Feature extraction from two-dimensional or higher-order data, such as face images and surveillance videos, have recently been an active research area. There have been several 2D or higher-order PCA-style dimensionality reduction algorithms, but they mostly lack probabilistic interpretations and are difficult to apply with, e.g., incomplete data. It is also hard to extend these algorithms for applications where a certain region of the data point needs special focus in the dimensionality reduction process (e.g., the facial region in a face image). In this paper we propose a probabilistic dimensionality reduction framework for 2D and higher-order data. It specifies a particular generative process for this type of data, and leads to better understanding of some 2D and higher-order PCA-style algorithms. In particular, we show it actually takes several existing algorithms as its (non-probabilistic) special cases. We develop efficient iterative learning algorithms within this framework and study the theoretical properties of the stationary points. The model can be easily extended to handle special regions in the high-order data. Empirical studies on several benchmark data and real-world cardiac ultrasound images demonstrate the strength of this framework.     

Effect analysis in higher-order languages

When programs are intended for parallel execution it becomes critical to determine whether the evaluations of two expressions can be carried out independently. We provide a scheme for making such determinations in a typed language with higher-order constructs and imperative features. The heart of our scheme is a mechanism for estimating thesupport of an expression, i.e., the set of global variables involved in its evaluation. This computation requires knowledge of all the aliases of an expression. The inference schemes are presented in a compositional fashion reminiscent of abstract interpretation. We prove the soundness of our estimates with respect to the standard semantics of the language.Supported by National Science Foundation Grant DCR-8602072.     

Minimization strategies for maximally parallel multiset rewriting systems

Maximally parallel multiset rewriting systems (MPMRS) give a convenient way to express relations between unstructured objects. The functioning of various computational devices may be expressed in terms of MPMRS (e.g., register machines and many variants of P systems). In particular, this means that MPMRS are Turing universal; however, a direct translation leads to quite a large number of rules. Like for other classes of computationally complete devices, there is a challenge to find a universal system having the smallest number of rules. In this article we present different rule minimization strategies for MPMRS based on encodings and structural transformations. We apply these strategies to the translation of a small universal register machine (Korec (1996) [9]) and we show that there exists a universal MPMRS with 23 rules. Since MPMRS are identical to a restricted variant of P systems with antiport rules, the results we obtained improve previously known results on the number of rules for those systems.     

Conditional Term Graph Rewriting with Indirect Sharing

For reasons of efficiency, term rewriting is usually implemented by term graph rewriting. In term rewriting, expressions are represented as terms, whereas in term graph rewriting these are represented as directed graphs. Unlike terms, graphs allow a sharing of common subexpressions. In previous work, we have shown that conditional term graph rewriting is a sound and complete implementation for a certain class of CTRSs with strict equality, provided that a minimal structure sharing scheme is used. In this paper, we will show that this is also true for two different extensions of normal CTRSs. In contrast to the previous work, however, a non-minimal structure sharing scheme can be used. That is, the amount of sharing is increased.     

Reachability and confluence are undecidable for flat term rewriting systems

Ground reachability, ground joinability and confluence are shown undecidable for flat term rewriting systems, i.e., systems in which all left and right members of rule have depth at most one.     

Conversion to tail recursion in term rewriting

Tail recursive functions are a special kind of recursive functions where the last action in their body is the recursive call. Tail recursion is important for a number of reasons (e.g., they are usually more efficient). In this article, we introduce an automatic transformation of first-order functions into tail recursive form. Functions are defined using a (first-order) term rewrite system. We prove the correctness of the transformation for constructor-based reduction over constructor systems (i.e., typical first-order functional programs).     

A Higher-Order Calculus for Graph Transformation

This paper presents a formalism for defining higher-order systems based on the notion of graph transformation (by rewriting or interaction). The syntax is inspired by the Combinatory Reduction Systems of Klop. The rewrite rules can be used to define first-order systems, such as graph or term-graph rewriting systems, Lafont's interaction nets, the interaction systems of Asperti and Laneve, the non-deterministic nets of Alexiev, or a process calculus. They can also be used to specify higher-order systems such as hierarchical graphs and proof nets of Linear Logic, or to specify the operational semantics of graph-based languages.     

Seat inventory control for sequential multiple flights with customer choice behavior

This paper considers a seat inventory control problem in which flights depart sequentially and passengers purchase available seats depending on customer choice behavior. Customer choice behavior can lead to either a horizontal shift or a booking loss when a desired fare class is unavailable. This problem is mathematically challenging and intractable via exact mathematical models. As an alternative heuristic approach, this paper develops a simulation-based greedy grid-search algorithm and illustrates simulation experiments using the newly developed algorithm. This paper obtains encouraging numerical results with the approach proposed here, but additional studies are required for accommodating more general assumptions such as booking arrival patterns, booking control mechanisms (e.g., cancellation and overbooking) and strategic customer behavior.     

Hierarchical Nominal Terms and Their Theory of Rewriting

Nominal rewriting introduced a novel method of specifying rewriting on syntax-with-binding. We extend this treatment of rewriting with hierarchy of variables representing increasingly 'meta-level' variables, e.g. in hierarchical nominal term rewriting the meta-level unknowns (representing unknown terms) in a rewrite rule can be 'folded into' the syntax itself (and rewritten). To the extent that rewriting is a mathematical meta-framework for logic and computation, and nominal rewriting is a framework with native support for binders, hierarchical nominal term rewriting is a meta-to-the-omega level framework for logic and computation with binders.     

A higher-order moment method of the lattice Boltzmann model for the Korteweg–de Vries equation

In this paper, a lattice Boltzmann model for the Korteweg–de Vries (KdV) equation with higher-order accuracy of truncation error is presented by using the higher-order moment method. In contrast to the previous lattice Boltzmann model, our method has a wide flexibility to select equilibrium distribution function. The higher-order moment method bases on so-called a series of lattice Boltzmann equation obtained by using multi-scale technique and Chapman–Enskog expansion. We can also control the stability of the scheme by modulating some special moments to design the dispersion term and the dissipation term. The numerical example shows the higher-order moment method can be used to raise the accuracy of truncation error of the lattice Boltzmann scheme.     

Counterexamples in infinitary rewriting with non-fully-extended rules

We show counterexamples exist to confluence modulo hypercollapsing subterms, fair normalisation, and the normal form property in orthogonal infinitary higher-order rewriting with non-fully-extended rules. This sets these systems apart from both fully-extended and finite systems, where no such counterexamples are possible.     

Behavioral Refinement of Graph Transformation-Based Models

Model-driven software engineering requires the refinement of abstract models into more concrete, platform-specific ones. To create and verify such refinements, behavioral models capturing recon- figuration or communication scenarios are presented as instances of a dynamic meta-model, i.e., a typed graph transformation system specifying the concepts and basic operations scenarios may be composed of. Possible refinement relations between models can now be described based on the corresponding meta-models.In contrast to previous approaches, refinement relations on graph transformation systems are not defined as fixed syntactic mappings between abstract transformation rules and, e.g., concrete rule expressions, but allow for a more loose, semantically defined relation between the transformation systems, resulting in a more flexible notion of refinement.     

Featherweight Java with dynamic and static overloading

We propose FMJ (Featherweight Multi Java), an extension of Featherweight Java with encapsulated multi-methods thus providing dynamic overloading. Multi-methods (collections of overloaded methods associated to the same message, whose selection takes place dynamically instead of statically as in standard overloading) are a useful and flexible mechanism which enhances re-usability and separation of responsibilities. However, many mainstream languages, such as, e.g., Java, do not provide it, resorting to only static overloading.The proposed extension is conservative and type safe: both “message-not-understood” and “message-ambiguous” are statically ruled out. Possible ambiguities are checked during type checking only on method invocation expressions, without requiring to inspect all the classes of a program. A static annotation with type information guarantees that in a well-typed program no ambiguity can arise at run-time. This annotation mechanism also permits modeling static overloading in a smooth way.Our core language can be used as the formal basis for an actual implementation of dynamic (and static) overloading in Java-like languages.     

A higher-order strategy for eliminating common subexpressions

Optimizing compilers often perform an operation known as common subexpression elimination to improve code efficiency. Typically this is accomplished either by pruning a directed acyclic graph to replace eliminated subexpressions by memory fetches of stored values or by using partial-redundancy elimination, a data-flow analysis method. In this paper a higher-order strategic method is presented that rewrites expression trees to eliminate common subexpressions using equivalences in the lambda calculus. This approach offers several advantages—it is intuitive, transformations can be defined and applied within a high-level rewrite system, and it uses transformations for which correctness preservation can be proven.