Automata-Based Program Optimization by Applying Requirement Transformations

V. I. Shelekhov, Head of Laboratory, A. P. Ershov Institute of Informatics Systems, Novosibirsk, Russia

Automata-based software engineering includes methods to develop simple, reliable and effective programs for reactive systems. A program is constructed as a finite state automation presented in the form of control state hypergraph. A production system language for describing the functional requirements is proposed as the specification language for automata-based programs. For development of an effective automata-based program presented by the production set, the optimizing requirement transformations are used. These methods are illustrated on the ATM adaptation layer (type 2) protocol. The presented version of Sender program for the AAL2 protocol is essentially simple and efficient in comparison with the same program published in the AAL2 standard.

The optimizing transformations are the followings: program specialization, superposition reduction, equivalence replacement, and simplifications. The transformations applied are not automatic. They are included in the user's program development process. For large switching programs, an essential optimization effect is obtained by replacing programs to equivalent hyperfunctions.

Keywords: program comprehension, automata-based programming, requirement specification, production system model, ATM Adaptation Layer

pp. 3–13