An algebraic approach to the design of compilers for object-oriented languages

In this paper we describe an algebraic approach to construct provably correct compilers for object-oriented languages; this is illustrated for programs written in a language similar to a sequential subset of Java. It includes recursive classes, inheritance, dynamic binding, recursion, type casts and test, assignment, and class-based visibility, but a copy semantics. In our approach, we tackle the problem of compiler correctness by reducing the task of compilation to that of program refinement. Compilation is identified with the reduction of a source program to a normal form that models the execution of object code. The normal form is generated by a series of correctness-preserving transformations that are proved sound from the basic laws of the language; therefore it is correct by construction. The main advantages of our approach are the characterisation of compilation within a uniform framework, where comparisons and translations between semantics are avoided, and the modularity and extensibility of the resulting compiler.     

An algebraic model for programming languages

The language of universal algebras is used as a model for programming language specification. BNF rules are employed for specifying the signature of the language algebra instead of the context free syntax. The algorithm for program evaluation is inductively defined by the following universal algebraic construction:

Any function defined on the generators of a free algebra taking values in the carrier of another similar algebra can be uniquely extended to a homomorphism between the two algebras.

Any conventional programming language can be specified by a finite set of BNF rules and its algebra of symbols is generated by a finite set of generator classes. Thus any function defined on the finite set of generators offers an algebraic mechanism for a universal algorithm for source language program evaluation.     

An algebraic approach to shape-from-image problems

This paper presents a new method for recovering three-dimensional shapes of polyhedral objects from their single-view images. The problem of recovery is formulated in a constrained optimization problem, in which the constraints reflect the assumption that the scene is composed of polyhedral objects, and the objective function to be minimized is a weighted sum of quadric errors of surface information such as shading and texture. For practical purpose it is decomposed into the two more tractable problems: a linear programming problem and an unconstrained optimization problem. In the present method the global constraints placed by the polyhedron assumption are represented in terms of linear algebra, whereas similar constraints have usually been represented in terms of a gradient space. Moreover, superstrictness of the constraints can be circumvented by a new concept ‘position-free incidence structure’. For this reason the present method has several advantages: it can recover the polyhedral shape even if image data are incorrect due to vertex-position errors, it can deal with perspective projection as well as orthographic projection, the number of variables in the optimization problem is very small (three or a little greater than three), and any kinds of surface information can be incorporated in a unifying manner.     

An algebraic approach to supervisory control

Supervisory control problems are formulated in terms of a process model where the mechanism of control is expressed in terms of an algebraic operator with the plant and supervision processes as its arguments. The solution subspaces for supervisory processes restrict the observation and the control capability of supervision. The main result corresponds to decentralized marked supervision under partial observations, and specific cases are derived from this result in a unified, algebraic way. The result and its derivation demonstrate the relative simplicity of the algebraic process formulation.     

An algebraic approach to feature interactions

The various approaches proposed to provide communication between CAD systems and process planning systems share the major problem that, due to geometric interactions among features, there may be several equally valid sets of manufacturable features describing the same part, and different sets of features may differ in their manufacturability. Thus, to produce a good process plan-or, in some cases, any plan at ll-it may be necessary to interpret the part as a different set of features than the one initially obtained from the CAD model. This is addressed using an algebra of features. Given a set of features describing a machinable part, other equally valid interpretations of the part can be produced by performing operations in the algebra. This will enable automated process planning systems to examine these interpretations in order to see which one is most appropriate for use in manufacturing. The feature algebra has been implemented for a restricted domain and integrated with the Protosolid solid modeling system and the EFHA process planning system     

An algebraic model for performance evaluation of timed event multigraphs

This note demonstrated that a certain class of Petri nets called timed-event multigraphs can be represented as a set of linear equations by using a novel dioid. With this new algebra, some properties are presented in the text. An example is discussed in the end, and an interesting result is computed.     

An algebraic approach to iterative learning control

In this paper discrete-time iterative learning control (ILC) systems are analysed from an algebraic point of view. The algebraic analysis shows that a linear-time invariant single-input–single-output model can always represented equivalently as a static multivariable plant due to the finiteness of the time-axis. Furthermore, in this framework the ILC synthesis problem becomes a tracking problem of a multi-channel step-function. The internal model principle states that for asymptotic tracking (i.e. convergent learning) it is required that an ILC algorithm has to contain an integrator along the iteration axis, but at the same time the resulting closed-loop system should be stable. The question of stability can then be answered by analysing the closed-loop poles along the iteration axis using standard results from multivariable polynomial systems theory. This convergence theory suggests that time-varying ILC control laws should be typically used instead of time-invariant control laws in order to guarantee good transient tracking behaviour. Based on this suggestion a new adaptive ILC algorithm is derived, which results in monotonic convergence for an arbitrary linear discrete-time plant. This adaptive algorithm also has important implications in terms of future research work—as a concrete example it demonstrates that ILC algorithms containing adaptive and time-varying components can result in enhanced convergence properties when compared to fixed parameter ILC algorithms. Hence it can be expected that further research on adaptive learning mechanisms will provide a new useful source of high-performance ILC algorithms.     

An algebraic approach to continuous collision detection for ellipsoids

We present algebraic expressions for characterizing three configurations formed by two ellipsoids in R³ that are relevant to collision detection: separation, external touching and overlapping. These conditions are given in terms of explicit formulae expressed by the subresultant sequence of the characteristic polynomial of the two ellipsoids and its derivative. For any two ellipsoids, the signs of these formulae can easily be evaluated to classify their configuration. Furthermore, based on these algebraic conditions, an efficient method is developed for continuous collision detection of two moving ellipsoids under arbitrary motions.     

An algebraic approach to revising propositional rule-based knowledge bases

One of the important topics in knowledge base revision is to introduce an efficient implementation algorithm. Algebraic approaches have good characteristics and implementation method; they may be a choice to solve the problem. An algebraic approach is presented to revise propositional rule-based knowledge bases in this paper. A way is firstly introduced to transform a propositional rule-based knowledge base into a Petri net. A knowledge base is represented by a Petri net, and facts are represented by the initial marking. Thus, the consistency check of a knowledge base is equivalent to the reachability problem of Petri nets. The reachability of Petri nets can be decided by whether the state equation has a solution; hence the consistency check can also be implemented by algebraic approach. Furthermore, algorithms are introduced to revise a propositional rule-based knowledge base, as well as extended logic programming. Compared with related works, the algorithms presented in the paper are efficient, and the time complexities of these algorithms are polynomial.     

An algebraic approach to decoupling in linear multivariable systems

This paper examines the problem of decoupling designs for linear multivariable systems. Both partial and diagonal decoupling designs are considered. The development is based on an algebraic approach and the use of coprime factorizations, which provide a mechanism to account for key system properties including internal stability and decoupling invariants. The results obtained include necessary and sufficient conditions for decoupling and a parametrization of all decoupling controllers.     

ADMiRe: an algebraic data mining approach to system performance analysis

Performance analysis of computing systems is an increasingly difficult task due to growing system complexity. Traditional tools rely on ad hoc procedures. With these, determining which of the manifold system and workload parameters to examine is often a lengthy and highly speculative process. The analysis is often incomplete and, therefore, prone to revealing faulty conclusions and not uncovering useful tuning knowledge. We address this problem by introducing a data mining approach called ADMiRe (analyzer for data mining results). In this scheme, regression analysis is first applied to performance data to discover correlations between various system and workload parameters. The results of this analysis are summarized in sets of regression rules. The user can then formulate intuitive algebraic expressions to manipulate these sets of rules to capture critical information. To demonstrate this approach, we use ADMiRe to analyze an Oracle database system running the TPC-C (Transaction Processing Performance Council) benchmark. The results generated by ADMiRe were confirmed by Oracle experts. We also show that by applying ADMiRe to Microsoft Internet Information Server performance data, we can improve system performance by 20 percent.     

Digital connectedness: An algebraic approach

Let E be the incidence matrix of a graph G having m nodes; then the number of connected components of G is equal to m ? r, where r is the rank of E. In particular, if G represents an adjacency relation between points in a digital picture (or higher-dimensional array), this shows that the connected components of points can be counted by computing the rank of E. Two proofs of this result are given, one based on results from algebraic topology and the other based on a self-contained graph-theoretic argument. The former proof can be generalized to yield a method of counting holes.     

An algebraic approach to the generation and description of binary pictures

An algebra is proposed for compactly generating and describing binary pictures such as textures and graphics. Four arithmetic operations, differentiation, and integration of such pictures are defined using pictorial constants and rational polynomials. Examples for these operations are illustrated.