Are there formal languages complete for SymSPACE(log n)? | SpringerLink
Skip to main content
Springer Nature Link
Log in

Are there formal languages complete for SymSPACE(log n)?

  • Chapter
  • First Online:
Foundations of Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 1337))

  • 281 Accesses

Abstract

This article discusses the existence of SymSPACE(logn)-complete formal languages. It is shown that a recent approach of Alvarez and Greenlaw to define symmetric versions of one-way devices doesn't lead to SymSPACE(log n) complete problems when applied to linear context-free or to one-counter languages.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. E. Allender, K.-J. Lange. Symmetry coincides with nondeterminism for time bounded auxiliary pushdown automata, in preparation, 1997.

    Google Scholar 

  2. C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Report TR96-039, ECCC, 6 1996.

    Google Scholar 

  3. R. Armoni, A. Ta-shma, A. Wigderson, and S. Zhou. SL 134-1 L 4/3. submitted, 1996.

    Google Scholar 

  4. D.A. Barrington. Bounded-width polynomial-size branching programs can recognize exactly those languages in NC 1. J. Comp. System Sci., 38:150–164, 1989.

    Article  MATH  MathSciNet  Google Scholar 

  5. Ka Wong Chong and Tak Wah Lam. Finding connected components in O(log n log log n) time on the EREW PRAM. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 11–20, 1993.

    Google Scholar 

  6. P. Flajolet and J. Steyaert. Complexity of classes of languages and operators. Rap. de Recherche 92, IRIA Laboria, Nov. 1974.

    Google Scholar 

  7. M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory Conference, pages 102–111, 1993.

    Google Scholar 

  8. P. Lewis and C.H. Papadimitriou. Symmetric space-bounded computation. Theoret. Comput. Sci., 19:161–187, 1982.

    Article  MathSciNet  Google Scholar 

  9. P. Lewis, R. Stearns, and J. Hartmanis. Memory bounds for recognition of context-free and context-sensitive languages. In Proc. 6th Annual IEEE Symp. on Switching Circuit Theory and Logical Design, pages 191–209, 1965.

    Google Scholar 

  10. N. Nisan. RL 134-1 SC. In Proc. of the 24th Annual ACM Symposium on Theory of Computing, pages 619–623, 1992.

    Google Scholar 

  11. W. Ruzzo. Tree-size bounded alternation. J. Comp. System Sci., 21:218–235, 1980.

    Article  MATH  MathSciNet  Google Scholar 

  12. E. Shamir and C. Beeri. Checking stacks and context-free programmed grammars accept p-complete languages. In Proc. of 2nd ICALP, number 14 in LNCS, pages 277–283. Springer, 1974.

    Google Scholar 

  13. I. Sudborough. A note on tape-bounded complexity classes and linear context-free languages. J. Assoc. Comp. Mach., 22:499–500, 1975.

    MATH  MathSciNet  Google Scholar 

  14. I. Sudborough. On tape-bounded complexity classes and multi-head finite automata. J. Comp. System Sci., 10:62–76, 1975.

    MATH  MathSciNet  Google Scholar 

  15. I. Sudborough. On the tape complexity of deterministic context-free languages. J. Assoc. Comp. Mach., 25:405–414, 1978.

    MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D72076, Tübingen

    Klaus -Jörn Lange

Authors
  1. Klaus -Jörn Lange
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Christian Freksa Matthias Jantzen Rüdiger Valk

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Lange, K.J. (1997). Are there formal languages complete for SymSPACE(log n)?. In: Freksa, C., Jantzen, M., Valk, R. (eds) Foundations of Computer Science. Lecture Notes in Computer Science, vol 1337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0052081

Download citation

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

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-63746-2

  • Online ISBN: 978-3-540-69640-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation