• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >One Queue or Two Pushdown Stores Take Square Time on a One-Head Tape Unit
【24h】

One Queue or Two Pushdown Stores Take Square Time on a One-Head Tape Unit

机译：一个队列或两个下推式商店在单头磁带机上占用正方形时间

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Simulation of one virtual queue or two virtual pushdown stores by one-head tape units is shown to take at least square time. Simulation means the implementation of the virtual queue or two pushdown stores on a one-head tape unit. Each multitape Turing machine can be simulated by a one-head tape unit in square time. A one-head tape as a synonym for a Turing machine with one single-head storage tape is used. A lower bound which matches this upper bound on simulation time, provides that in an oblivious Turing machine the movement of the storage tape heads is independent of the input and is a function of time alone. Kolmogorov's complexity method is used.

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号