An Implicit Recursive Language for the Polynomial Time-space Complexity Classes
Дата
Авторы
Covino,Emanuele
Pani,Giovanni
Journal Title
Journal ISSN
Volume Title
Издатель
Journal of Universal Computer Science
Аннотация
Описание
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(nk), 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.
Ключевые слова
time-space classes , implicit computational complexity , predicative recursion