Browse Prior Art Database

On One Tape Versus Two Stacks

IP.com Disclosure Number: IPCOM000148341D
Original Publication Date: 1984-Jan-31
Included in the Prior Art Database: 2007-Mar-29

Publishing Venue

Software Patent Institute

Related People

Li, Ming: AUTHOR [+2]

Abstract

i n g i

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 18

On One Tape Vernar Two Stacks
Ming Li

January 1984 .a :

v 1:{741


I.-{ :,. .. - . . - . ., -. ...

r;::x:~,?~rp,:-

~;~/q~:;;-i~,;,;; i ,t,,: ?\? 8 - - ..-,...- ' 1 x . , ' , J 3 \ ,

,**r,>,!,u:

\,\.:..#I 6 , . ...,' .:,:. :: .;:,.,; : '-::..*',, ,,.,

,: ,:<,.,:,..

. i,,:,,.,;i

. ;ji"',::!:.>!':

Department of Computer Science
Cornell University
I.thaca, New York 14853

[This page contains 1 picture or other non-text object]

Page 2 of 18

[This page contains 1 picture or other non-text object]

Page 3 of 18

On One Tape versus Two Stacks

~ i n g

~ i *

Department of Computer Science Cornell University
Ithaca, New York 14853

Abstract

   We develop a simple method which enables us to prove three new lower bounds (for both worst and average cases) for on-line computations, answering two open problems summarized in [DGPR].

   We give a language that requires R(n2) time for any 1-tape deterministic on- line machine, but it can be accepted by a Gstack 1-reversal bounded deterministic on-line machine in real time. This provides a tight lower bound, closing the gap between ~(n(lo~n)'/~)
lower bound by [P2] and the trivial 0(n2) upper bound.

   We also prove that 1-tape nondeterministic real time is much stronger than its deterministic version. For 1-tape on-line machines, we give language L (L") which is in nondeterministic linear (real) time but requires S2(n2) (Q(n'-5)) deterministic time.

   Finally we give a language which can be accepted by a 2-stack 1-reversal bounded deterministic machine in real time, but it requires f2(n1+ 'I2) time for any one tape nondeterministic online machine. This sharply improves an nlogn lower bound in [DGPR].

This work was supported in part by an NSF grant MCS-8301760.

[This page contains 1 picture or other non-text object]

Page 4 of 18

[This page contains 1 picture or other non-text object]

Page 5 of 18

1. Introduction

   Obtaining good lower bounds has been one of most important issues, of both practical and theoretical interests, in theoretical computer science. While nontrivial lower bounds for general models still seems beyond our grasp, there has been some success for restricted models, which does offer some insights and proof techniques. But even these proofs appeared to be quite hard.

   In this paper we will consider on-he computations which is generally used for investigating the dependency of the computational power on the number of tapes. We call a 'I34 M a k-tape on-line machine if M has a 1-way read only input tape and k working tapes. Without explicit indication, all the machines in this paper will be online machines. An on-line machine M works in red time if each time M reads an input symbol it makes only constant number of moves. A Zstack machine is like an usual pushdown automaton but with two pushdown stores. A k-stack machine is 1-reversal bounded if for each stack, once it starts popping, no m...