Concepedia

Turing Machine Space Bounds

Turing Machine Space Bounds is a theoretical construct in computational complexity theory that specifies the maximum amount of tape space a Turing machine requires to decide a language as a function of the input size, distinguishing it from time-based or circuit-based complexity measures.

40

Publications

2K

Citations

55

Authors

40

Institutions

Publications per year

2017–2026

0

Parents

Publications

40

On Relating Time and Space to Size and Depth

Allan Borodin · SIAM Journal on Computing · 1977 · 341 citations

, , +17

On Time Versus Space

John E. Hopcroft, Wolfgang J. Paul, Leslie G. Valiant · Journal of the ACM · 1977 · 255 citations · Full text

, , +17

The Complexity of Parallel Computations

James Wyllie · eCommons (Cornell University) · 1979 · 201 citations · Full text

, , +17

Deterministic CFL's are accepted simultaneously in polynomial time and log squared space

Stephen Cook · 1979 · 119 citations · Full text

, , +15

Space Lower Bounds for Maze Threadability on Restricted Machines

Stephen Cook, Charles Rackoff · SIAM Journal on Computing · 1980 · 109 citations

, , +14

1–5 of 40

Authors

55

  1. ÓH
    Óscar H. Ibarra

    University of California, Santa Barbara, United States

    4 publications · 79 citations

    4

    h-index

  2. SC
    Stephen Cook

    University of Toronto, Canada

    3 publications · 251 citations

    3

    h-index

  3. HC
    Hubert Comon

    Centre National de la Recherche Scientifique, France

    2 publications · 58 citations

    2

    h-index

  4. PB
    Paul Beame

    University of Washington, United States

    2 publications · 93 citations

    2

    h-index

  5. GM
    Giancarlo Mauri

    University of Milano-Bicocca, Italy

    2 publications · 38 citations

    2

    h-index

1–5 of 55

Institutions

40

  1. University of Toronto

    Toronto, Canada

    3 h-index

    3 publications

    483 citations

  2. Bielefeld University

    Bielefeld, Germany

    3 h-index

    3 publications

    289 citations

  3. University of Washington

    Seattle, United States

    2 h-index

    2 publications

    93 citations

  4. Yamaguchi University

    Yamaguchi, Japan

    2 h-index

    3 publications

    74 citations

  5. Massachusetts Institute of Technology

    Cambridge, United States

    2 h-index

    3 publications

    35 citations

  6. Cornell University

    Ithaca, United States

    2 h-index

    3 publications

    303 citations

  7. University of Milano-Bicocca

    Milan, Italy

    2 h-index

    9 publications

    165 citations

  8. University of Minnesota

    Minneapolis, United States

    2 h-index

    5 publications

    137 citations

1–8 of 40

Venues

  1. SIAM Journal on Computing

    9 publications · 644 citations

    9

    h-index

  2. Mathematical logic quarterly

    MLQ · 2 publications · 75 citations

    2

    h-index

  3. Information Sciences

    2 publications · 44 citations

    2

    h-index

  4. Journal of the ACM

    JACM · 2 publications · 308 citations

    2

    h-index

  5. Theoretical Computer Science

    2 publications · 49 citations

    2

    h-index

1–5