iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/3-540-10854-8_30
On the LBA problem | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the LBA problem

  • Conference paper
  • First Online:
Fundamentals of Computation Theory (FCT 1981)

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

Included in the following conference series:

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. Aho, A.V., J.E. Hopcroft and J.D. Ullman, (1968). Time and tape complexity of pushdown automaton languages, Info. and Control 13, pp. 186–206.

    Google Scholar 

  2. Aho, A.V., J.E. Hopcroft and J.D. Ullman, (1974) The design and analysis of computer algorithms, Addison-Wesley Publ. Comp., Reading, Massachussetts.

    Google Scholar 

  3. Alelinuas, R., R.M. Karp, R.J. Lipton, L. Lovasz and C. Rackhoff, (1979). Random walks, universal sequences and the complexity of maze problems, Proc. 20th IEEE Symp. on Foundations of Computer Science.

    Google Scholar 

  4. Book, R.V. (1972). On languages accepted in polynomial time, SIAM J. Computing 4, 281–287.

    Google Scholar 

  5. Book, R.V., (1976). Translational lemmas, polynomial time, and (log n)j-space, Theor. Comput. Sci. 1, pp 215–226.

    Google Scholar 

  6. Book, R.V., (1978). Simple representations of certain classes of languages, J.Ass. Comp. Mach. 25, 23–31.

    Google Scholar 

  7. von Braunmühl, B. and R. Verbeek, (1980). A recognition algorithm for deterministic CFLs optimal in time and space, Proc. 21st Annual Symp. Foundations of Computer Science pp. 411–420.

    Google Scholar 

  8. Chomsky, N., (1959). On certain formal properties of grammars, Inform. and Control 2, 133–167.

    Google Scholar 

  9. Chomsky, N., (1962). Context-free grammars and pushdown storage, Quart. Progr. Rept. No. 65, MIT, pp. 187–194.

    Google Scholar 

  10. Cook, S.A., (1970). Path Systems and language recognition, Proc. 2nd ACM Symp. Theory of Computing, 70–72.

    Google Scholar 

  11. Cook, S.A., (1971). Characterizations of pushdown machines in terms of time-bounded computers, J. Assoc. Comput. Mach. 18, pp. 4–18.

    Google Scholar 

  12. Cook, S.A., (1971). The complexity of theorem proving procedures, Proc. 3rd Annual ACM Symp. on Theory of Computing, 151–158.

    Google Scholar 

  13. Cook, S.A., (1979) Deterministic CFLs are accepted simultaneously in polynomial time and log squared space, Proc. 11th Annual ACM Symp. on Theory of Computing, 338–345.

    Google Scholar 

  14. Duris, P. and Z. Galil, (1980). Fooling a two-way automaton or One pushdown store is better than one counter for two-way machines, submitted for publication.

    Google Scholar 

  15. Galil, Z., (1977) Some open problems in the theory of computation as questions about two-way deterministic pushdown automata languages, Math. Systems Theory 10, pp. 211–218.

    Google Scholar 

  16. Garey, M.R. and D.S. Johnson, (1979). Computers and Intractability: A guide to the Theory of NP-Completeness, W.H. Freeman and Co., San Francisco.

    Google Scholar 

  17. Greibach, S.A., (1973). The hardest context-free language, SIAM J. Computing 2, pp. 304–310.

    Google Scholar 

  18. Greibach, S.A., (1977) A note on NSPACE(log n) and substitution, RAIRO Informatique théorique 11, 127–132.

    Google Scholar 

  19. Greibach, S.A., (1978) Remarks on blind and partially blind one-way multicounter machines, Theoretical Comp. Sci. 7, 311–324.

    Google Scholar 

  20. Hartmanis, J., (1972) On non-determinacy in simple computing devices, Acta Informatica, 334–336.

    Google Scholar 

  21. Hartmanis, J., (1978). On log-tape isomorphisms of complete sets, Theoretical computer Science 7, 273–286.

    Google Scholar 

  22. Hartmanis, J. and H.B. Hunt, (1973). The LBA problem and its importance in the theory of computing, Cornell University, Technical Report.

    Google Scholar 

  23. Hartmanis, J. and R.E. Stearns, (1965). On the computational complexity of algorithms, Transactions of American Math. Society 117, 285–306.

    Google Scholar 

  24. Hopcroft, J.E. and J.D. Ullman, (1969; new edition = 1979), Formal Languages and their Relation to Automata, Addison-Wesley, Reading. Mass., USA.

    Google Scholar 

  25. Jones, N.D. (1975). Space bounded reducibility among combinatorial problems, J. Comput. System Sci. 11, 62–85.

    Google Scholar 

  26. Jones, N.D., Y.E. Lien and W.T. Laaser. (1976). New problems complete for non-deterministic Log space, Math. Systems Theory 10, 1–17.

    Google Scholar 

  27. Jung, H., (1981), Relationships between probabilistic and deterministic tape complexity, submitted for publication.

    Google Scholar 

  28. Karp, R.M., (1972). Reducibility among combinatorial problems, in Complexity of Computer Computation, (R. Miller and J. Thatcher, eds.) Plenum Publishing Co., New York, pp. 85–103.

    Google Scholar 

  29. Kuroda, S.Y., (1964). Classes of languages and linear-bounded automata, Inform. and Control 7, 207–223.

    Google Scholar 

  30. Landweber, P.S. (1963). Three theorems on phrase structure grammars of type 1, Inform. and Control 6, 131–136.

    Google Scholar 

  31. Lewis, P.M., R.E. Stearns, and J. Hartmanis, (1965). Memory bounds for the recognition of context-free and context-sensitive languages, Proc. 6th Annual IEEE Cinf. on Switching Circuit Theory and Logical Design, pp. 191–202.

    Google Scholar 

  32. Monien, B., (1972). Relationships between pushdown automata and tape-bounded Turing machines, Proc. First Symp. on Automata Languages and Programming, North-Holland Publ. Comp. Amsterdam, pp. 575–583.

    Google Scholar 

  33. Monien, B. (1975). About the deterministic simulation of nondeterministic (logn)-tape bounded Turing machines, Lecture Notes in Comp. Sci. 33, Springer Verlag, pp. 118–126.

    Google Scholar 

  34. Monien, B., (1977). Transformational methods and their application to complexity problems, Acta Informatica 6, pp. 95–108, Corrigenda, Acta Informatica 8, pp. 383–384.

    Google Scholar 

  35. Monien, B., (1977). The LBA-problem and the deterministic tape complexity of two-way one-counter languages over a one-letter alphabet, Acta Informatica 8, 371–382.

    Google Scholar 

  36. Monien, B., (1977). About the derivation languages of grammars and machines, Lecture Notes in Comp. Sci. 52, Springer Verlag, pp. 337–351.

    Google Scholar 

  37. Monien, B. (1979) Connections between the LBA problem and the knapsack problem, Proceedings Frege-Konferenz, University Jena, pp. 262–280.

    Google Scholar 

  38. Monien, B., (1980). On a subclass of pseudonomial problems, Lecture Notes in Comp. Sci. 88, Springer Verlag, pp. 414–425.

    Google Scholar 

  39. Monien, B. and I.H. Sudborough, (1979). On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, Lecture Notes in Comp. Sci. 71, Springer Verlag, pp. 431–445.

    Google Scholar 

  40. Monien, B. and I.H. Sudborough, (1980). Bounding the bandwidth of NP-complete problems, Lecture Notes in Comp. Sci. 100, Springer Verlag, pp. 279–292.

    Google Scholar 

  41. Monien, B. and I.H. Sudborough, (1981). Bandwidth constrained NP-complete problems, Proc. 13th ACM Symp. Theory of Computing.

    Google Scholar 

  42. Myhill, J., (1960). Linear bounded automata, Wright Air Development Division, Tech. Note No. 60–165, Cincinnati, USA.

    Google Scholar 

  43. Rabin, M.O. and D. Scott, (1959). Finite automata and their decision problems, IBM.J.Res. 3:2, 115–125.

    Google Scholar 

  44. Ruby, S. and P.C. Fischer, (1965). Translational methods and computational comlexity, Proc. 6th Annual IEEE Conf. on Switching Circuit Theory and Logical Design, pp. 173–178.

    Google Scholar 

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

    Google Scholar 

  46. Savitch, W.J., (1973). A Note on multihead Automata and context-sensitive languages, Acta Informatica 2 (1973), pp. 249–252.

    Google Scholar 

  47. Schützenberger, M., (1963). Context-free languages and pushdown automata, Inform. and Control 6, 246–264.

    Google Scholar 

  48. Seiferas, J. I., (1977). Techniques for separating space complexity classes, J. Comput. System Sci. 14, pp. 73–99.

    Google Scholar 

  49. Seiferas, J.I., (1977). Relating refined space complexity classes, J. Comput. System Sci. 14, pp. 100–129.

    Google Scholar 

  50. Stearns R.E., J. Hartmanis, and P.M. Lewis II, (1965). Hierarchies of memory limited computations, Proc. 6th Annual IEEE Conf. on Switching Circuit Theory and Logical Design, 179–190.

    Google Scholar 

  51. Stockmeyer, L.J. and A.R. Meyer, (1973). Word problems requiring exponential time, Proc. 5th Annual ACM Symp. Theory of Comput. pp. 1–9.

    Google Scholar 

  52. Sudborough, I.H., (1975). A note on tape bounded complexity classes and linear context-free languages, J. Assoc. Comput. Mach. 22, pp. 500–501.

    Google Scholar 

  53. Sudborough, I.H., (1975). On tape bounded complexity classes and multihead finite automata, J. Comput. System Sci. 10, pp. 62–76.

    Google Scholar 

  54. Sudborough, I.H., (1977). Some remarks on multihead automata, R.A.I.R.O. Informatique théorique/Theoretical Computer Science II, pp. 181–195.

    Google Scholar 

  55. Sudborough, I.H., (1978). Relating open problems on the tape complexity of context-free languages and path system problems, Proc. Conf. on Info. Sciences and Systems, The John Hopkins University, Baltimore (USA).

    Google Scholar 

  56. Voelkel, L., (1979). Language recognition by linear bounded and copy programs, Proc. Fundamentals of Computation Theory, Akademie-Verlag Berlin, pp. 491–495.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Universität Paderborn, Paderborn, West - Germany

    Burkhard Monien

Authors
  1. Burkhard Monien
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Ferenc Gécseg

Rights and permissions

Reprints and permissions

Copyright information

© 1981 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Monien, B. (1981). On the LBA problem. In: Gécseg, F. (eds) Fundamentals of Computation Theory. FCT 1981. Lecture Notes in Computer Science, vol 117. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10854-8_30

Download citation

  • DOI: https://doi.org/10.1007/3-540-10854-8_30

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

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

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

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation