Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Reversal complexity

Published: 01 August 1991 Publication History

Abstract

No abstract available.

Cited By

View all

Recommendations

Reviews

Sekharipuram Subramaniam Ravi

The number of head reversals made during a Turing machine computation has been recognized as an important complexity measure because of its intimate connection to parallel time and circuit depth [1,2]. In this paper, the authors establish a number of important results on reversal complexity, including the following (note that f 2n is used to mean [ f n ]<__?__Pub Fmt kern Amount="1.5pt"> 2 ). A function f n is reversal-constructible if a two-tape Turing machine exists that, when given the unary representation of an integer n>0 , produces the unary representation of f n on one of its work tapes, using O f n reversals. The authors show that for any reversal-constructible function s n = W log n , DSPACE s n ? DREVERSAL s n . As the authors observe, this result in conjunction with Savitch's theorem [3] implies that for any reversal-constructible function s n = W log n , NSPACE s n ? DREVERSAL s 2 n . They also show that if the reversal-constructibility requirement on s n is removed, then DSPACE s n ? DREVERSAL s 2 n and that NSPACE s n ? DREVERSAL s 3 n . The authors prove the following tape reduction theorem for reversal complexity. Let r n = W log n . If L is a language accepted by a multi-tape Turing machine with at most r n reversals, then L is accepted by a two-tape Turing machine with at most O r 2 n reversals. The authors use the above tape reduction to prove a hierarchy theorem for reversal complexity. Specifically, they show that if f n and g n are functions such that g 2 n =o f n , g n = W log n , and f n is reversal-constructible, then a language L exists such that L ? DREVERSAL f n but L &nisin; DREVERSAL g n <__?__Pub Caret> . In establishing the above and other results, the authors develop a number of techniques that should prove useful in further work on reversal complexity. The paper is well written and includes a good summary of previous work in this area. I strongly recommend this paper and its companion<__?__Pub Fmt hardspace>[4] to anyone interested in complexity theory.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing
SIAM Journal on Computing  Volume 20, Issue 4
Aug. 1991
203 pages
ISSN:0097-5397
Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 August 1991

Author Tags

  1. complete languages
  2. parallel complexity
  3. reversal
  4. reversal hierarchies
  5. space
  6. tape reduction theorem

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2014)Tradeoff lower lounds for stack machinesComputational Complexity10.1007/s00037-012-0057-123:1(99-146)Online publication date: 1-Mar-2014
  • (2013)Two-Way Finite AutomataFundamenta Informaticae10.5555/2637657.2637663126:2-3(225-246)Online publication date: 1-Apr-2013
  • (2013)On the value of multiple read/write streams for data compressionInformation Theory, Combinatorics, and Search Theory10.5555/2555876.2555889(284-297)Online publication date: 1-Jan-2013
  • (2010)Grammar-based compression in a streaming modelProceedings of the 4th international conference on Language and Automata Theory and Applications10.1007/978-3-642-13089-2_23(273-284)Online publication date: 24-May-2010
  • (2009)On the Value of Multiple Read/Write Streams for Data CompressionProceedings of the 20th Annual Symposium on Combinatorial Pattern Matching - Volume 557710.5555/3127091.3127098(68-77)Online publication date: 22-Jun-2009
  • (2009)Machine models for query processingACM SIGMOD Record10.1145/1815918.181592238:2(18-28)Online publication date: 26-Oct-2009
  • (2009)Lower bounds for processing data with few random accesses to external memoryJournal of the ACM10.1145/1516512.151651456:3(1-58)Online publication date: 19-May-2009
  • (2007)Machine models and lower bounds for query processingProceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1265530.1265537(41-52)Online publication date: 11-Jun-2007
  • (2007)Lower bounds for randomized read/write stream algorithmsProceedings of the thirty-ninth annual ACM symposium on Theory of computing10.1145/1250790.1250891(689-698)Online publication date: 11-Jun-2007
  • (2007)Tight lower bounds for query processing on streaming and external memory dataTheoretical Computer Science10.1016/j.tcs.2007.02.062380:1-2(199-217)Online publication date: 20-Jul-2007
  • Show More Cited By

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media