Approach to the construction of algebraic models of algorithms and programs

DOI10.1007/BF02366576MaRDI QIDQ1364100zbMATH OpenOpenAlexFDO

Authors S. V. Surzhko, E. L. Yushchenko

Publication date 24 August 1997

Published in Cybernetics and Systems Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02366576

zbMATH Keywords

algorithmic algebrasOmega-regular element algebra

Mathematics Subject Classification ID

Abstract data types; algebraic specification (68Q65)

Review text

The article represents a new approach to construction of algebraic models of algorithms and programs. The basis of the approach is the algebra of Omega-regular elements. The algebra is distinguished from the algebra of regular expressions (Kleene algebra) by including one more operation in its signature, named herein as a characteristic. The algebra of Omega-regular element contains Kleene algebra. Besides, the Omega-regular elements define algorithms, which cannot be described in traditional terms of automata. In particular, conventional programming constructions defined by the means of deterministic and nondeterministic algorithmic algebra can be described in the terms of the considered algebra. The algebra in question includes objects which have not an adequate description in algorithmic algebras. In addition, the algebra of Omega-regular elements contains only four operations in comparison, for example, with algebra of nondeterministic algorithms, containing eight operations. Most attention is given to interpretations of Omega-regular element algebra in various classes of objects. The interpretation is the surjective homomorphism of considered algebra to the algebra which elements are objects of a given class. Examples are given. Connection with algorithmic algebras is shown. It is possible to consider the algorithmic algebra operations as derivative operations of Omega-regular element algebra. The set of the nondeterministic algebra operators (conditions) can strictly be put in the set of multiple-valued operators (accordingly -- in a Cartesian square of this set) of Omega-regular element algebra interpreted in a class of multiple-valued operators. The similar result is obtained for algebras of deterministic algorithms. The solvability of identity problem for nondeterministic algorithms algebra is proved on the base of the described approach.

Recommendations

• Complete interpretations of \(\Omega\)-languages and free algebras of \(\Omega\)-elements
• Omega algebras and regular equations
• scientific article; zbMATH DE number 3936508
• Identical transformations in algebras of nondeterministic algorithms. I

Cites work

• scientific article; zbMATH DE number 3177943 (Why is no real title available?)
• Identical transformations in algebras of nondeterministic algorithms. I
• On languages over an alphabet interpreted in a boolean algebra

Cited in

(7)

• Structural models of algorithms in problems of applied programming. II: Structural-algorithmic approach to software simulation
• Omega algebras and regular equations
• scientific article; zbMATH DE number 2130868 (Why is no real title available?)
• scientific article; zbMATH DE number 3847211 (Why is no real title available?)
• scientific article; zbMATH DE number 3872646 (Why is no real title available?)
• scientific article; zbMATH DE number 5181785 (Why is no real title available?)
• Formalization of algorithmic knowledge of object domains in terms of the algebra of algorithmics

This page was built for publication: Approach to the construction of algebraic models of algorithms and programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1364100)