Transformational reducibility and synthesis of algorithms and programs of symbolic processing

This paper deals with the algebra of algorithmics in the context of developing modern means of transformation and synthesis of algorithms and programs in object-oriented environments. This report was first presented by the author in English at the conference ECI-2005 (Kosice, Slovakia). __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 165–173, September–October 2006.     

Weakest pre-condition reasoning for Java programs with JML annotations

This paper distinguishes several different approaches to organising a weakest pre-condition (WP) calculus in a theorem prover. The implementation of two of these approaches for Java within the LOOP project is described. This involves the WP-infrastructures in the higher order logic of the theorem prover PVS, together with associated rules and strategies for automatically proving JML specifications for Java implementations. The soundness of all WP-rules has been proven on the basis of the underlying Java semantics. These WP-calculi are integrated with the existing Hoare logic, and together form a verification toolkit in PVS: typically one uses Hoare logic rules to break a large verification task up into smaller parts that can be handled automatically by one of the WP-strategies.     

The strong semantics for logic programs

Recently, the well-founded semantics of a logic programP has been strengthened to the well-founded semantics-by-case (WF_C) and this in turn has been strengthened to the extended well-founded semantics (WF_E). Both WF_C(P) and WF_E(P) have thelogical consequence property, namely, if an atomAj is true in the theory Th(P), thenAj is true in the semantics as well. However, neither WF_C nor WF_E has the GCWA property, i.e., if an atomAj is false in all minimal models ofP,Aj may not be false in WF_C(P) (resp. WF_E(P)). We extend the ideas in WF_C and WF_E to define a strong well-founded semantics WF_S which has the GCWA property. The strong semantics WF_S(P) is defined by combining GCWA with the notion ofderived rules. Here we use a new Type-III derived rules in addition to those used in WF_C and WF_E. The relationship between WF_S and WF_C is also clarified.     

A method for pogram analysis and Its applications to program-correctness problems

Described in this paper is a program-analysis method that can be used to effectively determine the logical structure of a program, explicate the computation a program will perform, and show the equivalence of programs. Applications to the problem areas in test-case generation, proving program correctness, and translation of “GOTO” programs into “GOTO-less” programs are discussed.     

Software tools for micro-analysis of programs

The paper proposes and describes several tools enabling their user to estimate the efficiency of Pascal or C-like programs. The approach consists of generating symbolic formulas expressing the efficiency of the programs being analyzed. The formulas are applicable to a variety of compiler-machine configurations. The actual numeric values of the variables in the symbolic formula are determined using linear programming techniques. The proposed approach reduces considerably the amount of benchmarking needed to analyze programs. Several examples are presented showing the applicability of the tools. The effort necessary to implement them is considerably reduced by the combined usage of Prolog and a symbolic formula manipulation package (Maple).     

The logic of Peirce algebras

Peirce algebras combine sets, relations and various operations linking the two in a unifying setting. This paper offers a modal perspective on Peirce algebras. Using modal logic a characterization of the full Peirce algebras is given, as well as a finite axiomatization of their equational theory that uses so-called unorthodox derivation rules. In addition, the expressive power of Peirce algebras is analyzed through their connection with first-order logic, and the fragment of first-order logic corresponding to Peirce algebras is described in terms of bisimulations.     

Prox-regularization of the dual method of centers for generalized fractional programs

We present in this paper a prox-dual regularization algorithm for solving generalized fractional programming problems. The algorithm combines the dual method of centres for generalized fractional programs and the proximal point algorithm and can handle nondifferentiable convex problems with possibly unbounded feasible constraints set. The proposed procedure generates two sequences of dual and primal values that approximate the optimal value of the considered problem respectively from below and from above at each step. It also generates a sequence of dual solutions that converges to a solution of the dual problem, and a sequence of primal solutions whose every accumulation point is a solution of the primal problem. For a class of problems, including linear fractional programs, the algorithm converges linearly.     

Using classes as specifications for automatic construction of programs in the NUT system

It is shown, how the object-oriented programming paradigm has been combined with automatic program construction in the NUT system: type information extracted from a class specification is being used for automatic construction of methods for the class. Special compute-messages are introduced as requests for program synthesis which can be done statically or dynamically. Particular features of the specification language which support the program synthesis are considered and applications of this method are outlined.     

Approximation schemes for deal splitting and covering integer programs with multiplicity constraints

We consider the problem of splitting an order for R goods, R≥1, among a set of sellers, each having bounded amounts of the goods, so as to minimize the total cost of the deal. In deal splitting with packages (DSP), the sellers offer packages containing combinations of the goods; in deal splitting with price tables (DST), the buyer can generate such combinations using price tables. Our problems, which often occur in online reverse auctions, generalize covering integer programs with multiplicity constraints (CIP), where we must fill up an R-dimensional bin by selecting (with a bounded number of repetitions) from a set of R-dimensional items, such that the overall cost is minimized. Thus, both DSP and DST are NP-hard, already for a single good, and hard to approximate for arbitrary number of goods.In this paper we focus on finding efficient approximations for DSP and DST instances where the number of goods is some fixed constant. In particular, we develop polynomial time approximation schemes (PTAS) for several subclasses of instances of practical interest. Our results include a PTAS for CIP in fixed dimension, and a more efficient (combinatorial) scheme for CIP_∞, where the multiplicity constraints are omitted. Our approximation scheme for CIP_∞ is based on a non-trivial application of the fast scheme for the fractional covering problem, proposed by Fleischer [L. Fleischer, A fast approximation scheme for fractional covering problems with variable upper bounds, in: Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithm, 2004, pp. 994-1003].     

Extended RKN methods with FSAL property for oscillatory systems

In this paper, we present extended RKN methods with FSAL property for numerical integration of perturbed oscillators. These numerical integrators are based on the extended Runge-Kutta-Nyström-type methods proposed by Yang et al. [H.L. Yang, X.Y. Wu, Xiong You, Y.L. Fang, Extended RKN-type methods for numerical integration of perturbed oscillators, Comput. Phys. Comm. 180 (2009) 1777-1794]. The numerical stability and phase property of the new methods are analyzed. The paper is accompanied by numerical experiments that demonstrate the effectiveness and robustness of our new methods in comparison with some well-known methods appeared in the scientific literature.     

A new neural network for solving nonlinear convex programs with linear constraints

In this paper, a new neural network was presented for solving nonlinear convex programs with linear constrains. Under the condition that the objective function is convex, the proposed neural network is shown to be stable in the sense of Lyapunov and globally converges to the optimal solution of the original problem. Several numerical examples show the effectiveness of the proposed neural network.     

Data race avoidance and replay scheme for developing and debugging parallel programs on distributed shared memory systems

Distributed shared memory (DSM) allows parallel programs to run on distributed computers by simulating a global virtual shared memory, but data racing bugs may easily occur when the threads of a multi-threaded process concurrently access the physically distributed memory. Earlier tools to help programmers locate data racing bugs in non-DSM parallel programs are not easily applied to DSM systems. This study presents the data race avoidance and replay scheme (DRARS) to assist debugging parallel programs on DSM or multi-core systems. DRARS is a novel tool which controls the consistency protocol of the target program, automatically preventing a large class of data racing bugs when the parallel program is subsequently run, obviating much of the need for manual debugging. For data racing bugs that cannot be avoided automatically, DRARS performs a deterministic replay-type function on DSM systems, faithfully reproducing the behavior of the parallel program during run time. Because one class of data racing bugs has already been eliminated, the remaining manual debugging task is greatly simplified. Unlike previous debugging methods, DRARS does not require that the parallel program be written in a specific style or programming language. Moreover, DRARS can be implemented in most consistency protocols. In this paper, DRARS is realized and verified in real experiments using the eager release consistency protocol on a DSM system with various applications.     

An Input/Output Semantics for Distributed Program Equivalence Reasoning

A new notion of input/output equivalence of distributed imperative programs, with synchronous communications, is introduced. It preserves the input/output relation, encompassing both, initial/final state and communication channel values. For its mathematical justification, the semantic framework of Manna and Pnueli, based on finite transition systems and reduced behaviors, is extended with the notion of input/output behavior. A set of laws for the equivalence is overviewed. A deduction rule for the substitution of references to input/output equivalent procedures is defined and justified in the new semantics. The rule is applied to decompose distributed program simplification proofs, introduced in a prior work, which use the laws to establish the equivalence between a sequential and a parallel communicating program. They include communication elimination as one of their steps. An outline of one of such proofs, for a pipelined processor model, is included.     

The Branching-Time Transformation Technique for Chain Datalog Programs

The branching-time transformation technique has proven to be an efficient approach for implementing functional programming languages. In this paper we demonstrate that such a technique can also be defined for logic programming languages. More specifically, we first introduce Branching Datalog, a language that can be considered as the basis for branching-temporal deductive databases. We then present a transformation algorithm from Chain Datalog programs to the class of unary Branching Datalog programs with at most one IDB atom in the body of each clause. In this way, we obtain a novel implementation approach for Chain Datalog, shedding at the same time new light on the power of branching-time logic programming.