Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Pebbling mountain ranges and its application to DCFL-recognition

  • Conference paper
  • First Online:
Automata, Languages and Programming (ICALP 1980)

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

Included in the following conference series:

Abstract

Recently, S.A. Cook showed that DCFL's can be recognized in O((log n)2) space and polynomial time simultaneously. We study the problem of pebbling mountain ranges (= the height of the pushdown-store as a function of time) and describe a family of pebbling strategies. One such pebbling strategy achieves a simultaneous O((log n)2/log log n) space and polynomial time bound for pebbling mountain ranges. We apply our results to DCFL recognition and show that the languages of input-driven DPDA's can be recognized in space O((log n)2/log log n). For general DCFL's we obtain a parameterized family of recognition algorithms realizing various simultaneous space and time bounds. In particular, DCFL's can be recognized in space O((log n)2) and time O(n2.87) or space O(√n log n) and time O(n1.5 log log n) or space O(n/log n) and time O(n(log n)3). More generally, our methods exhibit a general space-time tradeoff for manipulating pushdownstores (e.g. run time stack in block structured programming languages).

Full version of paper is available from author

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.

Similar content being viewed by others

References

  • S.A. Cook: Deterministic CFL's are accepted simultaneously in polynomial time and log squared tape, 11th ACM Symposium on Theory of Computing, 1971, 338–345

    Google Scholar 

  • E.M. Gurari, O.H. Ibarra: On the space complexity of recursive algorithm, Inf. Proc. Letters, Vol. 8, No. 5, 1979, 267–272

    Google Scholar 

  • B. Schmidt: Ph.D. Thesis, Universität des Saarlandes, Fachbereich 10, 6600 Saarbrücken, in preparation

    Google Scholar 

  • S. Swami, J. Savage: Space-Time Tradeoffs for linear Recursion, 6th ACM Symposium on Principles of Programming Languages, 1979, 135–142

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. FB 10, Universität des Saarlandes, 6600, Saarbrücken, West Germany

    Kurt Mehlhorn

Authors
  1. Kurt Mehlhorn
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jaco de Bakker Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 1980 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Mehlhorn, K. (1980). Pebbling mountain ranges and its application to DCFL-recognition. In: de Bakker, J., van Leeuwen, J. (eds) Automata, Languages and Programming. ICALP 1980. Lecture Notes in Computer Science, vol 85. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10003-2_89

Download citation

  • DOI: https://doi.org/10.1007/3-540-10003-2_89

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10003-4

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation