1. SCSIT
  2. Всі випуски
  3. Випуск 672, 2010
  4. The Extended Algebra of Algorithms With Multiconditional Elimination

The Extended Algebra of Algorithms With Multiconditional Elimination

SCSIT.
2010;
Випуск 672
: cc. 291 - 300
Authors: 

V. Ovsyak1,2, A. Ovsyak3

1Department of Computer Science, Ukrainian University of Printing
2Department of Electrical, Control and Computer Engineering, Opole University of Technology, Poland
3Kyiv National University of Culture and Arts, The L’vov Campus

The existing, intuitive computation models, that is the virtual machines of Turing, Post, Kolmogorov, Schönhage, Aho-Ullman-Hopcroft as well as the algorithms of Markov and Krinitski, and the recursive functions, all lack precise, mathematical formulation. Consequently, an algebra of algorithms is defined using the axiomatic method. The algebra is based on the operations of sequencing, elimination, paralleling and reversing as well as cyclic sequencing, cyclic elimination and cyclic paralleling, all of them performed on the so-called uniterms. A useful extension is offered in terms of multiconditional elimination. An example illustrates the usefulness of the algebra of algorithms.

Вказано відомі методи інтуїтивного опису алгоритмів, якими є віртуальні машини Т’юрінга, Поста, Колмогорова, Шонгаґе, Ахо-Ульмана-Хопкрофта, а також алгоритми Маркова і Крініцкого та рекурсивні функції, засобами яких алгоритми описуються не формалізовано. Дефініцію розширеної алгебри алгоритмів подано аксіоматичним методом. Алгебра базується на операціях секвентування, багатозначного елімінування, паралелення і реверсування, а також циклічного секвентування, циклічного еліміну- вання та циклічного паралелення, які виконуються над унітермами. Розширення торкається введення операції багатозначного елімінування. Прикладом проілюстрована ефективність розширеної алгебри алгоритмів.

модель
операція
алгоритм
означення
  1. Kleene S.C.: Origins of recursive function theory. Annals of the Theory of Computing, vol. 3, No. 1, Jan. 1981, pp. 52-67.
  2. Turing A. M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of London Mathematical Society, series 2, vol. 42 (1936-1937), pp. 230-265; correction, ibidem, vol. 43, pp. 544-546. Reprinted in [13 Davis M., pp. 155-222] and available online at http://www.abelard.org/turpap2/tp2-ie.asp.
  3. Kleene S.C.: Turing’s analysis of computability, and major applications of it. In Rolf Herken, Editor, The universal Turing machine: A half-century story, Oxford University Press, 1988, pp. 17-54.
  4. Post E. L.: Finite Combinatory Processes – Formulation 1.Journal of Symbolic Logic, 1, pp. 103-105, 1936. Reprinted in The Undecidable, pp. 289ff.
  5. De Mol L.: Closing the circle: an analysis of Emil Post’s early work. The Bulletin of Symbolic Logic, Vol. 12, Issue 02, June 2006, pp. 267 — 289.
  6. Kolmogorov A.N.: On the concept of algorithm (in Russian). Uspekhi Mat. Nauk 8:4 (1953), pp. 175-176; translated into English in Uspensky V.A., Semenov A.L.: Algorithms: Main Ideas and Applications, Kluwer, 1993.
  7. Kolmogorov A.N., Uspensky V.A.: On the definition of algorithm (in Russian). Uspekhi Mat. Nauk 13:4 (1958), pp. 3-28; translated into English in AMS Translations 29 (1963), pp. 217-245.
  8. Gurevich Y.: Kolmogorov machines and related issues. In G. Rozenberg and A. Salomaa, Editors, Current Trends in Theoretical Computer Science, World Scientific, 1993, pp. 225-234; originally in Bull. EATCS 35 (1988).
  9. Schönhage A.: Universelle Turing Speicherung. In J. Dörr and G. Hotz, Editors, Automatentheorie und Formale Sprachen, Bibliogr. Institut, Mannheim, 1970, pp. 369-383.
  10. Schönhage A.: Storage modification machines. SIAM Journal on Computing, 9 (1980), pp. 490-508.
  11. Markov A.A.: Theory of algorithms (in Russian). Editions of Academy of Sciences of the USSR, vol. 38, 1951, pp. 176-189; translated into English in American Mathematical Society Translations, 1960, series 2, 15, pp. 1-14.
  12. Markov A.A., Nagorny N.M.: The Theory of Algorithms (Mathematics and its Applications). Springer, 2001.
  13. Church A.: An unsolvable problem of elementary number theory. American Journal of Mathematics, vol. 58 (1936), pp. 345-363.
  14. Constable R.L., Smith S.F. Computational foundations of basic recursive function theory. Theoretical Computer Science, 121, pp. 89- 112, Dec. 1993.
  15. Sieg W.: Step by recursive step: Church’s analysis of effective calculability. The Bulletin of Symbolic Logic, 3:2 (1997), pp. 154-180.
  16. Aho A.V, Hopcroft J.E, Ullman J.D.: The design and analysis of computer algorithms. Addison-Wesley Publishing Company, 1974.
  17. Krinitski N.A.: Algorithms around us (in Russian). Mir, Moscow, 1988; also translated to Spanish (Algoritmos a nuestro alrededor).
  18. Uspensky V.A., Semenov A.L.: Algorithms: Main Ideas and Applications. Kluwer, 1993.
  19. Barendregt H.P., The Lambda Calculus: Its Syntax and Semantics, North Holland, Amsterdam, 1984.
  20. Davis M., Computability and Unsolvability, Mcgraw-Hill, 1985.
  21. Ovsyak V.K., Ovsyak O.V, Ovsyak J.V.: Theory of Abstract Algorithms and Mathematical Modelling of Information Systems (in Polish), Opole University of Technology Press, Opole, Poland, 2005.
  22. Ovsyak V.K.: Computation Models and Algebra of Algorithms. http://www.nbuv.gov.ua/Portal/natural/VNULP/ISM/ 2008_621/01.pdf 
  23. Ovsyak V.K., Latawiec K.J., Ovsyak O.V.: Applications of the algebra of algorithms – a sequential method for the synthesis of formulae of algorithms. Submitted for the CiE’2010 Conference.