The dependence condition graph: Precise conditions for dependence between program points

The problem of identifying the conditions under which semantic or behavioural dependences arise between different program statements has interesting applications in various areas such as program understanding, software maintenance, software audits and software testing. We present an extension to the program dependence graph (PDG), called the dependence condition graph (DCG), that enables identifying the conditions for dependence between program points. We show that these conditions are not only correct with respect to the program's semantics, but also more precise than identified by other known techniques. We also present evidence that the DCG is a practical representation and can be built for large programs, and sketch many different applications of the DCG.     

BALSEQ: a basic program to balance and sequence univariant reactions about invariant points

BALSEQ is an interactive BASIC program that will determine the sequence of stable univariant reactions about a stable invariant point. User input to BALSEQ consists of the number of components and phases, their identities, and the composition of each phase. BALSEQ combinatorially generates each invariant point and each reaction at each invariant point, and then uses Schreinemaker's rules to determine the actual sequence of reactions. Chemographically degenerate reactions are treated properly by the program and are listed twice only when both ends of the reaction are stable.     

Unique fixed points vs. least fixed points

The aim of this paper is to compare two approaches to the semantics of programming languages: the least fixed point approach, and the unique fixed point approach. Briefly speaking, we investigate here the problem of existence of extensions of algebras with the unique fixed point property to ordered algebras with the least fixed point property, that preserve the fixed point solutions. We prove that such extensions always exist, the construction of a free extension is given. It is also shown that in some cases there is no ‘faithful’ extension, i.e. some elements of a carrier are always collapsed.     

Splitting iteration method for simple singular points and simple bifurcation points

A splitting iteration method is introduced to compute the simple singular points and the simple bifurcation points of nonlinear problems. It needs little computational work and converges with an adjustable rate. Numerical examples are presented.     

Approximation of a set of points by points of a grid

A procedure is given for translating a rectangular grid in such a way that a finite set of points in ?^N is approximated as good as possible by points of the translated grid.     

Template-based program verification and program synthesis

Program verification is the task of automatically generating proofs for a program’s compliance with a given specification. Program synthesis is the task of automatically generating a program that meets a given specification. Both program verification and program synthesis can be viewed as search problems, for proofs and programs, respectively. For these search problems, we present approaches based on user-provided insights in the form of templates. Templates are hints about the syntactic forms of the invariants and programs, and help guide the search for solutions. We show how to reduce the template-based search problem to satisfiability solving, which permits the use of off-the-shelf solvers to efficiently explore the search space. Template-based approaches have allowed us to verify and synthesize programs outside the abilities of previous verifiers and synthesizers. Our approach can verify and synthesize difficult algorithmic textbook programs (e.g., sorting and dynamic programming-based algorithms) and difficult arithmetic programs.     

Occlusion points identification algorithm

In this paper a very simple and efficient algorithm is proposed, to calculate the invisible regions of a scene, or shadowed side of a body, when it is observed from a pre-set point. This is done by applying a deterministic numerical procedure to the portion of scene in the field of view, after having been projected in the observer reference frame. The great advantage of this approach is its generality and suitability for a wide number of applications. They span from real time renderings, to the simulation of different types of light sources, such as diffused or collimated, or simply to calculate the effective visible surface for a camera mounted on board of an aircraft, in order to optimize its trajectory if remote sensing or aerial mapping task should be carried out. Optimizing the trajectory, by minimizing at any time the occluded surface, is also a powerful solution for a search and rescue mission, because a wider area in a shorter time can be observed, particularly in situations where the time is a critical parameter, such as, during a forest fire or in case of avalanches. For its simplicity of implementation, the algorithm is suitable for real time applications, providing an extremely accurate solution in a fraction of a millisecond. In this paper, the algorithm has been tested by calculating the occluded regions of a very complex mountainous scenario, seen from a gimbal-camera mounted on board of a flying platform.     

Least fixed points revisited

Parameter mechanisms for recursive procedures are investigated. Contrary to the view of Manna et al..it is argued that both call-by-value and call-by-name mechanisms yield the least fixed points of the functionals determined by the bodies of the procedures concerned. These functionals differ, however, according to the mechanism chosen. A careful and detailed presentation of this result is given, along the lines of a simple typed lambda calculus, with interpretation rules modelling program execution in such a way that call-by-value determines a change in the environment and call-by-name a textual substitution in the procedure body.     

Cluster points and stability

The relationship is examined between the stability properties of the solution of the discrete time system where A(·): R ⁿ →R ⁿ is a continuous non-linear map, and the set of cluster points L(x*) of the sequence {x_i } _i=0 ^∞. We show that the sequence is bounded if and only if the set L(x*) is contained in a compact set. We review also the contributions of other authors in this area.     

Reference points and roughness

In this paper, we introduce the notion of a reference point and provide local approximations for a subset of the universe. The notion of a reference point naturally gives rise to a rough approximations framework, wherein several approximations are possible on the same set. Also, we present an extension to the decision theoretic rough set model by using reference points.     

Direct dominance of points

Several transitive relations of geometrical objects (like inclusion of intervals on a line or polygons in the plain), which are important in VLSI design applications, can be translated into the dominance relation a dominates b iff (a ≠ b and a _j ≧ b _j for j = 1,…d) of points a = (a ₁,...,a _d ),b = (b ₁,…b _d ) in R ^d by representing the objects as points in a suitable way. If only the transitive reduction (see [7]) of the given relation is required and not all the implications by transitivity, one can restrict oneself to the direct dominances in the corresponding point set N; here a dominates b directly means that a dominates b and there is no—with respect to dominance—intermediate c in N (see [5]). To estimate the advantage of this restriction, information about the numbers of dominant and directly dominant pairs in a set of n points is required, both numbers essentially depending upon how the points are distributed in R ^d . In this paper we assume the n points in question to be identically and independently distributed; then we can expect q·n·(n–1) dominance pairs. For a certain class of distributions including the uniform distribution we prove the theorem, that the expected number of direct dominance pairs is asymptotically equal to 1/(d?1)! · n1n ^{d ? 1}(n). Hence algorithms which compute only the direct dominances instead of all dominances are worth to be considered.     

Pascal-P,program structure and program behaviour

This note describes some interesting results observed during the implementation of Pascal-P upon a Data General NOVA computer. A significant performance improvement was obtained by altering the program structure of the Pascal-P compiler to reflect the dynamic behaviour of the program. Some implications of this behaviour for the design of computer architectures are discussed.     

The program dependence graph in static program testing

In this paper, new techniques for static program testing are presented. The techniques are based on the program dependence graph, which models the structure of the program in terms of data and control dependences between program instructions. First, a new approach for redundant code detection is proposed. The main idea is based on the observation that each program instruction should have influence on the output of the program, otherwise it is considered redundant. Second, an input-output relationship analysis, which reflects the influence of specific input data on specific output data of the program, is proposed. It is shown that the presented techniques can increase the number of detectable errors as compared with error detection through data flow analysis alone.     

Classifying points for sweeping solids

Many diverse engineering problems can be modeled with solid sweeping in a conceptually simple and intuitive way, and sweeps are considered to be one of the basic representation schemes in solid modeling. However, many properties of sweeps as well as their “informational completeness” are not well understood, which is the primary reason why computational support for solid sweeping remains scarce. We propose a generic point membership classification (PMC) for sweeping solids of arbitrary complexity moving according to one parameter affine motions. The only restrictive assumption that we make in this paper is that the initial and final configurations of the moving object do not intersect during the sweep. Our PMC test is defined in terms of inverted trajectory tests against the original geometric representation of the generator object, which implies that this test can be implemented in any geometric representation that supports curve-solid intersections. Importantly, this PMC test provides complete geometric information about the set swept by 3-dimensional objects in general motions. At the same time, it establishes the foundations for developing a new generation of computational tools for sweep boundary evaluation and trimming, as well as a number of practical applications such as shape synthesis, contact analysis and path planning.