Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-26T08:48:51.487Z Has data issue: false hasContentIssue false
  • English
  • Français

Tailoring recursion for complexity

Published online by Cambridge University Press:  12 March 2014

Erich Grädel  and
Yuri Gurevich
Erich Grädel
Affiliation:
Lehrgebiet Math. Grundlagen der Informatik, RWTH Aachen, D-52056 Aachen, Germany, E-mail: [email protected]
Yuri Gurevich
Affiliation:
EECS Department, University of Michigan, Ann Arbor, MI 48109-2122, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 AC1 -circuits.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 60 , Issue 3 , September 1995 , pp. 952 - 969
Copyright
Copyright © Association for Symbolic Logic 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Abiteboul, S. and Vianu, V., Datalog extensions for database queries and updates, Journal of Computer and System Sciences, vol. 43 (1991), pp. 62–124.CrossRefGoogle Scholar
[2]Balcázar, J., Díaz, J., and Gabarró, J., Structural complexity, vol. I and II, Springer Verlag, 1988–1990.CrossRefGoogle Scholar
[3]Bellantoni, S. and Cook, S., A new recursion-theoretic characterization of the polytime functions, Proceedings of the 24th ACM Symposium on the Theory of Computing, Association for Computing Machinery, 1992, pp. 283–293.Google Scholar
[4]Büchi, J., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[5]Buss, S., Bounded arithmetic, Bibliopolis, 1986.Google Scholar
[6]Cobham, A., The intrinsic computational difficulty of functions, Logic, methodology and philosophy of science (Bar-Hillel, Y., editor), vol. II, North-Holland, Amsterdam, 1965.Google Scholar
[7]Compton, K. and Laflamme, C., An algebra and a logic for NC1, Information and Computation, vol. 87 (1990), pp. 241–263.CrossRefGoogle Scholar
[8]Fagin, R., Generalized first-order spectra and polynomial-time recognizable sets, Proceedings of the SIAM-AMS, vol. 7 (1974), pp. 43–73.Google Scholar
[9]Goerdt, A., Characterizing complexity classes by general recursie definitions in higher types, Proceedings of the 2nd workshop on Computer Science Logic CSL '88, Lecture Notes in Computer Science, no. 385, Springer, 1989, pp. 99–117.Google Scholar
[10]Grädel, E., Capturing complexity classes by fragments of second order logic, Theoretical Computer Science, vol. 101 (1992), pp. 35–57.CrossRefGoogle Scholar
[11]Grädel, E. and Otto, M., Inductive definability with countingon finite structures, Proceedings of the CSL '92, Lecture Notes in Computer Science, Springer, 1993, pp. 231–247.Google Scholar
[12]Gurevich, Y., Algebras offeasible functions, Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, vol. 24 (1983), pp. 210–214.Google Scholar
[13]Gurevich, Y., Toward logic tailored for computational complexity, Computation and Proof Theory (Richter, M. M.et al., editors), Lecture Notes in Mathematics, no. 1104, Springer, 1984, pp. 175–216.CrossRefGoogle Scholar
[14]Gurevich, Y., Logic and the challenge of computer science, Trends in Theoretical Computer Science (Börger, E., editor), Computer Science Press, 1988, pp. 1–57.Google Scholar
[15]Gurevich, Y. and Lewis, H., A logic for constant-depth circuits, Information and Control, vol. 61 (1984), pp. 65–74.CrossRefGoogle Scholar
[16]Gurevich, Y. and Shelah, S., Fixed point extensions of first order logic, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 265–280.CrossRefGoogle Scholar
[17]Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computing System Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
[18]Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
[19]Immerman, N., Languages that capture complexity classes, SIAM Journal of Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
[20]Immerman, N., Nondeterministic space is closed under complementation, SIAM Journal of Computing, vol. 17 (1988), pp. 935–939.CrossRefGoogle Scholar
[21]Immerman, N., Descriptive and computational complexity, Computational Complexity Theory, Proceedings of Symposia in Applied Mathematics (Hartmanis, J., editor), vol. 38, American Mathematical Society, 1989, pp. 75–91.CrossRefGoogle Scholar
[22]Krentel, M., The complexity of optimization problems, Journal of Computer and System Sciences, vol. 36 (1988), pp. 490–509.CrossRefGoogle Scholar
[23]Livchak, A., The relational model for process control, Automatic documentation and mathematical linguistics, vol. 4 (1983), pp. 27–29, (in Russian).Google Scholar
[24]Lo, Libo, Functions and functionals on finite systems, this Journal, vol. 57 (1992), pp. 118–130.Google Scholar
[25]Sanonov, V., Polynomial computability and recursivity in finite domains, Elektronische Datenverarbeitung und Kybernetik, vol. 16 (1980), pp. 319–323.Google Scholar
[26]Szelepcsényi, R., The method of forced enumeration for nondeterministic automata, Acta Informatica, vol. 26 (1988), pp. 279–284.CrossRefGoogle Scholar
[27]Trakhtenbrot, B., Finite automata and the logic of monadic predicates, Doklady Akademii Nauk SSR, vol. 140 (1961), pp. 326–329.Google Scholar
[28]Vardi, M., Complexity of relational query languages, Proceedings of the 14th Symposium on Theory of Computing, vol. 14 (1982), pp. 137–146.Google Scholar