Stratified functional programs and computational complexity

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Stratified functional programs and computational complexity

Full text

Pdf (936 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Charleston, South Carolina, United States

Pages: 325 - 333

Year of Publication: 1993

ISBN:0-89791-560-7

Author

Daniel Leivant

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 17, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/158511.158659 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	Axt65	P. Axt, Iteration of primitive recursion, Zeit. f'fir mathematische Logik u. Grundlagen d. Math 11 (1965) 253-255.
	BC92	Stephen Bellantoni , Stephen Cook, A new recursion-theoretic characterization of the polytime functions, Computational Complexity, v.2 n.2, p.97-110, 1992 [doi>10.1007/BF01201998]
	Blo92	Stephen Bloch, Functional characterizations of uniform log-depth and polylog-depth circuit families, to ~I>- pear in the Proceedings of the 1992 IEEE Conference on Structure in Complexity.
	CKS81	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	CL90	Kevin J. Compton , Claude Laflamme, An algebra and a logic for NC, Information and Computation, v.87 n.1-2, p.241-263, July/August 1990 [doi>10.1016/0890-5401(90)90063-N]
	Clo90	Peter Clote, Sequential machine-independent characterizations o/the parallel complexity classes ALOG- TIME, A C~, NCk and NC, in Samuel M. Buss & Philip 3. Scott (eds.), Feasible Mathematics, Perspectives in Computer Science, Birkhauser-Boston, New York (1990).
	Cob65	A. Cobham, The intrinsic computational difficulty o//unctions, in Y. Bar-Hillel (ed.), Proceedings of the International Conference on Logic, Methodology, and Philosophy of Science, North-Holland, Amsterdam (1962) 24-30.
	Göd58	Kurt GSdel, {)bet eine bisher noch nicht beniite Erweiterung des finiten Standpunktes, Dialeetiea 12 (1958), 280-287. Republished with English translation and explanatory notes by A. S. Troelstra in Kurt GSdeh Collected Works (Oxford University Press, 1990), vol. II, ed. S. Feferman.
	Grz53	A. Grzegorczyk, Some classes of recursive functions, Rozprawy Mate. IV, Warsaw, 1953.
	Gur83	Yuri Gurevich, Algebras o/ feasible }unctions, Twenty Fourth Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1983, 210-214.
	Gur87	Yuri Gurevich, Logic and the challenge o/Computer Science, in Current Trends in Theoretical Computer Science, (Egon BSrger, editor), Computer Science Press, 1987.
	Hei61	W. Heinermann, Untersuchungen iiber die Rekursionszahlen rekursiver Funktionen, Dissertation, Universit~t Munster, 1961.
	Lei87	D. Leivant, Descriptive characterizations of computational complexity, Journal of Computer and System Sciences, v.39 n.1, p.51-83, Aug. 1989 [doi>10.1016/0022-0000(89)90019-6]
	Lei90	Daniel Leivant, Subrecursion and lambda representation over free algebras (Preliminary Summary), in Samuel M. Buss & Philip J. Scott (eds.), Feasible Mathematics, Perspectives in Computer Science, Birkhauser-Boston, New York (1990) 281-291.
	Lei90a	Daniel Leivant, Discrete polymorphism, Proceedings of the 1990 ACM conference on LISP and functional programming, p.288-297, June 27-29, 1990, Nice, France [doi>10.1145/91556.91675]
	Lei91	Daniel Leivant, A .foundational delineation of computational feasibility, in Proceedings of the Sixth IEEE Conference on Logic in Computer Science (Amstcrdaxn), IEEE Computer Society Press, Wa~shington, D.C., 1991.
	Lei93	Daniel Leivant, A foundational delineation of poly-time, Papers presented at the IEEE symposium on Logic in computer science, p.391-420, May 1994, Amsterdam, The Netherlands
	Lei9?	Daniel Leivant, Predicative Peano theories, to appear.
	Lei9?a	Daniel Leivant, Predicative recurrence in finite types, to appear.
	LM93	Daniel Leivant , Jean-Yves Marion, Lambda calculus characterizations of poly-time, Fundamenta Informaticae, v.19 n.1-2, p.167-184, Sept./Oct. 1993
	Mul73	H. Mfiller, Characterization of the elementary functions in terms of depth o{ nesting of primitive recursions, Recursive Function Theory Newsletters 5 (1973) 14-15. Initially reported in Dissertation, Universit~t Miinster, 1973(?).
	Pap85	Christos Papadimitriou, A note on the expressive power o/PROLOG, Bull. EATCS 26 (June 1985) 21- 23.
	Pet66	Rdsza Pdter, Rekursive Funktionen, Akaddmiai Kiad6, Budapest, 1966. English translation: Recursive Functions, Academic Press, New York, 1967.
	Ros84	H.E. Rose, Subrecursion, Clarendon Press (Oxford University Press), Oxford, 1984.
	Saz80	Vladimir Sazonov, Polynomial computability and recursivity in finite domains, Eleetronisehe Informationsverarbeitung und Kybernetik 7 (1980) 319- 323.
	Schw69	Helmut Schwichtenberg, Rekursionszahlen und die Grzegorczyk-Hierarchie, Archiv/'dr mathematische Log\|k 12 (1969) 85-97.

CITED BY 7

	Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000
	Martin Hofmann, The strength of non-size increasing computation, ACM SIGPLAN Notices, v.37 n.1, p.260-269, Jan. 2002
	Martin Hofmann, Linear types and non-size-increasing polynomial time computation, Information and Computation, v.183 n.1, p.57-85, May 25, 2003
	M. Hofmann , P. J. Scott, Realizability models for BLL-like languages, Theoretical Computer Science, v.318 n.1-2, p.121-137, June 2004
	L. Kristiansen , K.-H. Niggl, On the computational complexity of imperative programming languages, Theoretical Computer Science, v.318 n.1-2, p.139-161, June 2004
	Salvatore Caporaso , Emanuele Covino , Giovanni Pani, A predicative approach to the classification problem, Journal of Functional Programming, v.11 n.1, p.95-116, January 2001
	Ugo Dal Lago, The geometry of linear higher-order recursion, ACM Transactions on Computational Logic (TOCL), v.10 n.2, p.1-38, February 2009