# On the Comparative Complexity of Primitive Recursive Arithmetical and String Functions

## 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 *SH _{AW}* and

*SH*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

_{WA}*SH*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].

_{AW}## 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

## How to Cite

*Mathematical Problems of Computer Science*,

*39*, 81–87. Retrieved from http://mpcs.sci.am/index.php/mpcs/article/view/424

## Issue

## Section

## License

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