Subrecursive Programming Languages, Part I
- 1 July 1972
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 19 (3) , 526-568
- https://doi.org/10.1145/321707.321721
Abstract
The structural complexity of programming languages, and therefore of programs as well, can be measured by the subrecursive class of functions which characterize the language. Using such a measure of structural complexity, we examine the tradeoff relationship between structural and computational complexity. Since measures of structural complexity directly related to high level languages interest us most, we use abstract language models which approximate highly struc+, "-,., + =, (~) : ~* & ¢~* £. ) ...... ""Keywords
This publication has 11 references indexed in Scilit:
- An Overview of the Theory of Computational ComplexityJournal of the ACM, 1971
- The enumerability and invariance of complexity classesJournal of Computer and System Sciences, 1971
- Notes on avoiding “go to” statementsInformation Processing Letters, 1971
- On the size of machinesInformation and Control, 1967
- Some definitional suggestions for automata theoryJournal of Computer and System Sciences, 1967
- A Machine-Independent Theory of the Complexity of Recursive FunctionsJournal of the ACM, 1967
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965
- Random-Access Stored-Program Machines, an Approach to Programming LanguagesJournal of the ACM, 1964
- Classes of predictably computable functionsTransactions of the American Mathematical Society, 1963
- A Hierarchy of Primitive Recursive FunctionsMathematical Logic Quarterly, 1963