Skip to main content
SpringerLink
Log in

Logical and schematic characterization of complexity classes

  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

We consider classes of well-known program schemes from a complexity theoretic viewpoint. We define logics which express all those problems solvable using our program schemes and show that the class of problems so solved or expressed coincides exactly with the complexity classPSPACE (our problems are viewed as sets of finite structures over some vocabulary). We derive normal form theorems for our logics and use these normal form theorems to show that certain problems concerning acceptance and termination of our program schemes and satisfiability of our logical formulae arePSPACE-complete. Moreover, we show that a game problem, seemingly disjoint from logic and program schemes, isPSPACE-complete using the results described above. We also highlight similarities between the results of this paper and the literature, so providing the reader with an introduction to this area of research.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barwise, J.: An introduction to first-order logic. In: Barwise, J. (ed.) Handbook of mathematical logic, pp. 5–46, Amsterdam, North-Holland 1977

    Google Scholar 

  2. Brown, S., Gries, D., Szymanski, T.: Universality of data retrieval languages. Sixth Symposion on Principles of Programming Languages 1979, pp. 110–117

  3. Cook, S.: Characterizations of push-down machines in terms of time-bounded computers. J. ACM18 (1) 4–18 (1971)

    Google Scholar 

  4. Constable, R., Gried, D.: On classes of program schemata. SIAM J. Comput.1 (1) 66–118 (1972)

    Google Scholar 

  5. Courcelle, B.: Some applications of logic of universal algebra, and of category theory to the theory of graph transformations. Bull. EAT CS36, 161–218 (1988)

    Google Scholar 

  6. Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of computation. SIAM-AMS7, 27–41 (1974)

  7. Friedman, H.: Algorithmic procedures, generalized Turing algorithms and elementary recursion theory. In: Gandy, R.O., Yates, C.M.E. (eds.) Logic Colloquiium 1969, pp. 361–390. Amsterdam: North-Holland 1971

    Google Scholar 

  8. Garey, M.R., Johnson, D.S.: Computers and intractability. San Francisco: W.H. Freeman 1979

    Google Scholar 

  9. Gurevich, Y.: Toward logic tailored for computational complexity. In: Richter, M.M., Börger, E., Oberschelp, W., Schinzel, B., Thomas, W. (eds.) Computation and proof theory (Lect. Notes Math., vol. 1104, pp. 175–216), Berlin Heidelberg New York: Springer 1984

    Google Scholar 

  10. Gurevich, Y.: Logic and the challenge of computer science. University of Michigan Tech. Rep. CRL-TR-10-85, 1985

  11. Harel, D.: First-order dynamic logic (Lect. Notes Comput. Sci., vol. 68) Berlin Heidelberg New York: Springer 1979

    Google Scholar 

  12. Harel, D.: Dynamic logic. Handbook of philosophical logic II. Dordrecht: Reidel 1984

    Google Scholar 

  13. Harel, D., Peleg, D.: On static logics, dynamic logics, and complexity classes. Inf. Control60, 86–102 (1984)

    Google Scholar 

  14. Immerman, N.: Number of quantifiers is better than number of tape cells. J. Comput. Syst. Sci.22, 65–72 (1981)

    Google Scholar 

  15. Immerman, N.: Upper and lower bounds for first-order expressibility. J. Comput. Syst. Sci.25 (1), 76–98 (1982)

    Google Scholar 

  16. Immerman, N.: Languages that capture complexity classes. SIAM J. Comput.16 (4), 760–778 (1987)

    Google Scholar 

  17. Immerman, N.: Expressibility as a complexity measure: results and directions. Proc. Second Structure in Complexity Theory Conf., 1987, pp. 194–202

  18. Immerman, N.: Descriptive and computational complexity. Manuscript.

  19. Immerman, N.: Nondeterministic space is closed under complementation. Proc. Third IEEE Structure in Complexity Theory Conf., 1988, pp. 112–115

  20. Jones, N.D., Muchnik, S.S.: Even simple programs are hard to analyze. J. ACM24 (2), 338–350 (1977)

    Google Scholar 

  21. Paterson, M., Hewitt, N.: Comparative schematology. Record of Project MAC Conf. on Concurrent Systems and Parallel Computation, pp. 119–128. New York: ACM 1970

    Google Scholar 

  22. Rogers jr., H.: Theory of recursive functions and effective computability. New York: McGraw-Hill 1967

    Google Scholar 

  23. Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci.4, 177–192 (1970)

    Google Scholar 

  24. Spaan, E., Torenvliet, L., Emde Boas van, P.: Nondeterminism, fairness, and a fundamental analogy. Bull. EAT CS37, 186–193 (1989)

    Google Scholar 

  25. Stewart, I.A.: Expressibility, complexity, and comparative schematology. University of Newcastle upon Tyne Tech. Rep., No. 273, 1988

  26. Stewart, I.A.: Logical and schematic characterization of complexity classes. University of Newcastle upon Tyne Tech. Rep., No. 290, 1989

  27. Stockmeyer, L.J.: The polynomial-time hierarchy. Theor. Comput. Sci.3, 1–22 (1977)

    Google Scholar 

  28. Tiuryn, J., Urzyczyn, P.: Some relationships between logics of programs and complexity theory. Theor. Comput. Sci.60, 83–108 (1988)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computing Laboratory, University of Newcastle upon Tyne, Claremont Tower, Claremont Road, NE1 7RU, Newcastle upon Tyne, England

    Iain A. Stewart

Authors
  1. Iain A. Stewart
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Stewart, I.A. Logical and schematic characterization of complexity classes. Acta Informatica 30, 61–87 (1993). https://doi.org/10.1007/BF01200263

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01200263

Keywords

Search

Navigation