On the computational complexity of imperative programming languages. (English) Zbl 1048.03030
Summary: Two restricted imperative programming languages are considered: One is a slight modification of a loop language studied intensively in the literature, the other is a stack programming language over an arbitrary but fixed alphabet, supporting a suitable loop concept over stacks. The paper presents a purely syntactical method for analysing the impact of nesting loops on the running time. This gives rise to a uniform measure \(\mu\) on both loop and stack programs, that is, a function that assigns to each such program P a natural number \(\mu\)(P) computable from the syntax of P.
It is shown that stack programs of \(\mu\)-measure \(n\) compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class \(\mathcal E^{n+2}\). In particular, stack programs of \(\mu\)-measure 0 compute precisely the polynomial-time computable functions.
Furthermore, it is shown that loop programs of \(\mu\)-measure \(n\) compute exactly the functions in \(\mathcal E^{N+2}\). In particular, loop programs of \(\mu\)-measure 0 compute precisely the linear-space computable functions.
It is shown that stack programs of \(\mu\)-measure \(n\) compute exactly those functions computed by a Turing machine whose running time lies in Grzegorczyk class \(\mathcal E^{n+2}\). In particular, stack programs of \(\mu\)-measure 0 compute precisely the polynomial-time computable functions.
Furthermore, it is shown that loop programs of \(\mu\)-measure \(n\) compute exactly the functions in \(\mathcal E^{N+2}\). In particular, loop programs of \(\mu\)-measure 0 compute precisely the linear-space computable functions.
MSC:
| 03D10 | Turing machines and related notions |
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 03D20 | Recursive functions and relations, subrecursive hierarchies |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68N15 | Theory of programming languages |
Keywords:
Implicit computational complexity; Imperative programming languages; Subrecursion theory; Grzegorczyk hierarchy; Polynomial-time computabilityReferences:
| [1] | S.J. Bellantoni, Predicative recursion and computational complexity, Ph.D. Thesis, Toronto, September 1993.; S.J. Bellantoni, Predicative recursion and computational complexity, Ph.D. Thesis, Toronto, September 1993. |
| [2] | Bellantoni, S. J., Predicative recursion and the polytime hierarchy, (Clote, P.; Remmel, J., Feasible Mathematics II, Perspectives in Computer Science (1994), Birkhäuser: Birkhäuser Basel), 15-29 · Zbl 0841.03022 |
| [3] | Bellantoni, S. J.; Cook, S., A new recursion-theoretic characterization of the polytime functions, Comput. Complexity, 2, 97-110 (1992) · Zbl 0766.68037 |
| [4] | Bellantoni, S. J.; Niggl, K.-H., Ranking primitive recursionsthe low Grzegorczyk classes revisited, SIAM J. Comput., 29, 2, 401-415 (2000) · Zbl 0939.03042 |
| [5] | Bellantoni, S. J.; Niggl, K.-H.; Schwichtenberg, H., Higher type recursion, ramification and polynomial time, Ann. Pure Appl. Logic, 104, 17-30 (2000) · Zbl 0959.03027 |
| [6] | Bloch, S., Function-algebraic characterizations of log and polylog parallel time, Comput. Complexity, 4, 2, 175-205 (1994) · Zbl 0813.68099 |
| [7] | Clote, P., Computation models and function algebra, (Griffor, E., Handbook of Computability Theory (1996), Elsevier: Elsevier Amsterdam) · Zbl 0942.68049 |
| [8] | P. Clote, A safe recursion scheme for exponential time, in: S. Adian, A. Nerode (Eds.), Lecture Notes in Computer Science, Vol. 1234, Springer, Berlin, 1997, pp. 44-52.; P. Clote, A safe recursion scheme for exponential time, in: S. Adian, A. Nerode (Eds.), Lecture Notes in Computer Science, Vol. 1234, Springer, Berlin, 1997, pp. 44-52. · Zbl 0888.03029 |
| [9] | Goetze, B.; Nehrlich, W., The structure of loop programs and subrecursive hierarchies, Z. Math. Logik Grundlag. Math., 26, 255-278 (1980) · Zbl 0439.03018 |
| [10] | A. Grzegorczyk, Some classes of recursive functions, Rozprawy Mat., Vol. IV, Warszawa, 1953.; A. Grzegorczyk, Some classes of recursive functions, Rozprawy Mat., Vol. IV, Warszawa, 1953. · Zbl 0052.24902 |
| [11] | W. Heinermann, Untersuchungen über die Rekursionszahlen rekursiver Funktionen, Ph.D. Thesis, Münster, 1961.; W. Heinermann, Untersuchungen über die Rekursionszahlen rekursiver Funktionen, Ph.D. Thesis, Münster, 1961. |
| [12] | M. Hofmann, Type systems for polynomial-time computation, Habilitation Thesis, TU Darmstadt, 1998.; M. Hofmann, Type systems for polynomial-time computation, Habilitation Thesis, TU Darmstadt, 1998. |
| [13] | Leivant, D., Subrecursion and lambda representation over free algebras, (Buss, S.; Scott, P., Feasible Mathematics, Perspectives in Computer Science (1990), Birkhäuser: Birkhäuser Boston, New York), 281-291 · Zbl 0772.03020 |
| [14] | D. Leivant, A foundational delineation of computational feasibility, in: Proc. Sixth IEEE Conf. on Logic in Computer Science (Amsterdam), IEEE Computer Society Press, Washington, DC, 1991.; D. Leivant, A foundational delineation of computational feasibility, in: Proc. Sixth IEEE Conf. on Logic in Computer Science (Amsterdam), IEEE Computer Society Press, Washington, DC, 1991. |
| [15] | D. Leivant, Stratified functional programs and computational complexity, in: Conf. Record of the 20th Annual ACM Symposium on Principles of Programming Languages, New York, 1993, pp. 325-333.; D. Leivant, Stratified functional programs and computational complexity, in: Conf. Record of the 20th Annual ACM Symposium on Principles of Programming Languages, New York, 1993, pp. 325-333. |
| [16] | Leivant, D., Ramified recurrence and computational complexity I: Word recurrence and poly-time, (Clote, P.; Remmel, J., Feasible Mathematics II, Perspectives in Computer Science (1994), Birkhäuser: Birkhäuser Basel), 320-343 · Zbl 0844.03024 |
| [17] | Leivant, D., Predicative recurrence in finite type, (Nerode, A.; Matiyasevisch, Y. V., Logical Foundations of Computer Science. Logical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 813 (1994), Springer: Springer Berlin), 227-239 · Zbl 0947.03065 |
| [18] | Leivant, D.; Marion, J.-Y., Lambda calculus characterizations of poly-time, Fund. Inform., 19, 167-184 (1993) · Zbl 0781.68059 |
| [19] | D. Leivant, J.-Y. Marion, Ramified recurrence and computational complexity IV: predicative functionals and poly-space, Inform. Comput., to appear.; D. Leivant, J.-Y. Marion, Ramified recurrence and computational complexity IV: predicative functionals and poly-space, Inform. Comput., to appear. · Zbl 1044.03526 |
| [20] | Machthey, M., Augmented loop languages and classes of computable functions, J. Comput. System Sci., 6, 603-624 (1972) · Zbl 0312.68028 |
| [21] | A.R. Meyer, D.M. Ritchie, The complexity of loop programs, in: Proc. ACM Nat. Conf., 1967, pp. 465-469.; A.R. Meyer, D.M. Ritchie, The complexity of loop programs, in: Proc. ACM Nat. Conf., 1967, pp. 465-469. |
| [22] | H. Müller, Klassifizierungen der primitiv rekursiven Funktionen, Ph.D. thesis, Münster, 1974.; H. Müller, Klassifizierungen der primitiv rekursiven Funktionen, Ph.D. thesis, Münster, 1974. |
| [23] | Niggl, K.-H., The \(μ\)-measure as a tool for classifying computational complexity, Arch. Math. Logic, 39, 515-539 (2000) · Zbl 0964.03041 |
| [24] | A. Nguyen, A formal system for linear-space reasoning, M.Sc. Thesis, University of Toronto, 1993; available as T.R. 330/96.; A. Nguyen, A formal system for linear-space reasoning, M.Sc. Thesis, University of Toronto, 1993; available as T.R. 330/96. |
| [25] | Oitavem, I., New recursive characterizations of the elementary functions and the functions computable in polynomial space, Rev. Math. Univ. Complutense Madrid, 10, 1, 109-125 (1997) · Zbl 0872.03028 |
| [26] | Parsons, C., Hierarchies of primitive recursive functions, Z. Math. Logik Grundlag. Math., 14, 357-376 (1968) · Zbl 0172.29703 |
| [27] | Ritchie, R. W., Classes of predictably computable functions, Trans. Amer. Math. Soc., 106, 139-173 (1963) · Zbl 0107.01001 |
| [28] | Rose, H. E., Subrecursion, Functions and Hierarchies (1984), Clarendon Press: Clarendon Press Oxford · Zbl 0539.03018 |
| [29] | Schwichtenberg, H., Rekursionszahlen und die Grzegorczyk-Hierarchie, Arch. Math. Logik Grundlag., 12, 85-97 (1969) · Zbl 0213.01801 |
| [30] | Simmons, H., The realm of primitive recursion, Arch. Math. Logic, 27, 177-188 (1988) · Zbl 0659.03025 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
