Approach to the construction of algebraic models of algorithms and programs (Q1364100)

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.