文章基本信息

标题：An Implicit Recursive Language for the Polynomial Time-space Complexity Classes
作者：Emanuele Covino ; Giovanni Pani
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：2002
卷号：8
期号：1
页码：75-84
出版社：Graz University of Technology and Know-Center
摘要：
Abstract: We define a language over an algebra of words by means of a version of predicative recursion, and we prove that it represents a resource-free characterization of the computations performed by a register machine in time O(n^k), for each denite k; starting from this result, and by means of a restricted form of composition, we give a characterization of the computations of a register machine with a polynomial bound simultaneously imposed over time and space complexity.