Reports on Mathematical Logic

No. 30


Zdzislaw GRODZKI and Jerzy MYCKA

THE NEW CLASSES OF MARKOV-LIKE k-ALGORITHMS

A b s t r a c t. This paper continues the line initiated in [Z. Grodzki, J. Mycka The equivalence of some classes of algorithms] of uniform formalization of some classes of formal algorithms. The successive new classes ${\cal RMA}_k$ and $\overline{{\cal RMA}_k}$ of right-hand side Markov-like $k$-algorithms are introduced. The classes ${\cal RMA}_k$ and $\overline{{\cal RMA}_k}$ of algorithms are "symmetric" to the classes ${\cal MA}_k$ and $\overline{{\cal MA}_k}$ of left-hand side Markov-like $k$-algorithms which have been introduced in [Z. Grodzki, J. Mycka The equivalence of some classes of algorithms]. The equivalence of the classes ${\cal RMA}_k$ and $\overline{{\cal RMA}_k}$ and the class ${\cal MNA}$ of Markov normal algorithms is shown here. This implies the closure properties of the above classes under the same operations as of ${\cal MNA}$.


Back to Main Menu