On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions

Authors

  • Igor D. Zaslavsky Institute for Informatics and Automation Problems of NAS RA
  • Mikayel H. Khachatryan Institute for Informatics and Automation Problems of NAS RA

Keywords:

string function, arithmetical function, term, alphabetic enumeration, Shannon function, primitive recursive function

Abstract

Formal languages LA and LW are introduced as in [1] for the representation of primitive recursive arithmetical and string functions. Shannon functions SHAW and SHWA describing the relations between the complexities of functions representations in these languages are defined as in [1]. A new proof of the upper bounds for SHAW is presented; it is based on a new method giving in some cases new possibilities for applications in comparison with the methods considered in [1].

References

M. H. Khachatryan. “On the Representation of Arithmetical and String Functions in Formal Languages,” Transactions of IIAP of NAS of RA, Mathematical Problems of Computer Science, vol. 27, pp. 37-53, 2006.

A. I. Maltsev. Algorithms and Recursive Functions. 2nd Edition, Moskow, Nauka , 1986 (in Russian).

Downloads

Published

2021-12-10

How to Cite

Zaslavsky, I. D., & Khachatryan, M. H. (2021). On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions. Mathematical Problems of Computer Science, 39, 81–87. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/424

Issue

Vol. 39 (2013): Mathematical Problems of Computer Science

Section

Articles

License

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.