• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>SOFSEM 2009: Theory and practice of computer science >On Stateless Deterministic Restarting Automata
【24h】

On Stateless Deterministic Restarting Automata

机译：无状态确定性重启自动机

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The transitions of a stateless automaton do not depend on internal states but solely on the symbols currently scanned by its heads accessing the input or memory. We investigate stateless deterministic restarting automata that, after executing a rewrite step, continue to read their tape before performing a restart. Even the weakest class thus obtained contains the regular languages properly. The relations between different classes of stateless automata as well as between stateless automata and the corresponding types of automata with states are investigated, and it is shown that the language classes defined by the various types of deterministic stateless restarting automata without auxiliary symbols are anti-AFLs that are not even closed under reversal.
机译：无状态自动机的转换不依赖于内部状态，而仅取决于其头部访问输入或存储器时当前扫描的符号。我们研究了无状态确定性重新启动自动机，该自动机在执行重写步骤之后，在执行重新启动之前继续读取其磁带。这样获得的最弱的一类也正确地包含了常规语言。研究了无状态自动机的不同类别之间以及无状态自动机与具有状态的相应自动机类型之间的关系，并且表明由各种类型的无辅助符号的确定性无状态自动机定义的语言类别是反AFL甚至没有在逆转中关闭。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号