Journal of Symbolic Logic 60 (3):952-969 (1995)
| Abstract |
We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC 1 -circuits
|
| Keywords | No keywords specified (fix it) |
| Categories | (categorize this paper) |
| DOI | 10.2307/2275767 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 71,489
External links
- From the Publisher via CrossRef (no proxy)
- citeseerx.ist.psu.edu
(no proxy) - projecteuclid.org (no proxy)
- projecteuclid.org [2] (no proxy)
- journals.cambridge.org (no proxy)
- jstor.org (no proxy)
- jstor.org [2] (no proxy)
- jstor.org [3] (no proxy)
- cambridge.org (no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.
Fixed-Point Extensions of First-Order Logic.Yuri Gurevich & Saharon Shelah - 1986 - Annals of Pure and Applied Logic 32:265-280.
Citations of this work BETA
No citations found.
Similar books and articles
Functional Complexity in Organisms: Parts as Proxies. [REVIEW]Daniel W. McShea - 2000 - Biology and Philosophy 15 (5):641-668.
An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras.Martin Hofmann - 1997 - Bulletin of Symbolic Logic 3 (4):469-486.
Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997.M. M. Arslanov & Steffen Lempp (eds.) - 1999 - W. De Gruyter.
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.S. B. Cooper, T. A. Slaman & S. S. Wainer (eds.) - 1996 - Cambridge University Press.
Computability, an Introduction to Recursive Function Theory.Nigel Cutland - 1980 - Cambridge University Press.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Euclidean Functions of Computable Euclidean Domains.Rodney G. Downey & Asher M. Kach - 2011 - Notre Dame Journal of Formal Logic 52 (2):163-172.
Classical Recursion Theory: The Theory of Functions and Sets of Natural Numbers.Piergiorgio Odifreddi - 1989 - Sole Distributors for the Usa and Canada, Elsevier Science Pub. Co..
Analytics
Added to PP index
2009-01-28
Total views
20 ( #560,831 of 2,520,891 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,891 )
2009-01-28
Total views
20 ( #560,831 of 2,520,891 )
Recent downloads (6 months)
1 ( #405,457 of 2,520,891 )
How can I increase my downloads?
Downloads
