Presentation	2005-04-18 On time and space complexity of functions Kenya UENO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Similar to the computable function class, it is known that many function complexity classes like FP and FPSPACE can be expressed by recursion theoretic scheme. Based on these results, we introduce a new notion of operators for general function complexity classes. We construct an operator which characterizes the relation between time and space bounded function complexity classes. Moreover, we introduce new classes composed of functions whose output lengths are restricted to the input length plus some constant and characterize FP and FPSPACE by using these classes and operators. Furthermore, we define a notion of completeness for FPSPACE and show a FPSPACE-complete function.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Function Complexity Classes / Recursive Function Theory / Operators
Paper #	COMP2005-4
Date of Issue

Conference Information
Committee	COMP
Conference Date	2005/4/11(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	On time and space complexity of functions
Sub Title (in English)
Keyword(1)	Function Complexity Classes
Keyword(2)	Recursive Function Theory
Keyword(3)	Operators
1st Author's Name	Kenya UENO
1st Author's Affiliation	Department of Computer Science Graduate School of Information Science and Technology the University of Tokyo()
Date	2005-04-18
Paper #	COMP2005-4
Volume (vol)	vol.105
Number (no)	7
Page	pp.pp.-
#Pages	6
Date of Issue