...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Hybrid one-dimensional reversible cellular automata are regular
【24h】

Hybrid one-dimensional reversible cellular automata are regular

机译：混合一维可逆细胞自动机是规则的

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

摘要

It is shown that the set of hybrid one-dimensional reversible cellular automata (CA) with the periodic boundary condition is a regular set. This has several important consequences. For example, it allows checking whether a given CA is reversible and the random generation of a reversible CA from the uniform distribution, both using time polynomial in the size of the CA. Unfortunately, the constant term in the resulting random generation algorithm is much too large to be of practical use. We show that for the less general case of null boundary (NB) CA, this constant can be reduced drastically, hence facilitating a practical algorithm for uniform random generation. Our techniques are further applied asymptotically to count the number of reversible NBCA. (c) 2007 Elsevier B.V. All rights reserved.
机译：结果表明，具有周期性边界条件的混合一维可逆细胞自动机（CA）集是规则集。这有几个重要的后果。例如，它允许使用CA大小中的时间多项式来检查给定的CA是否可逆以及从均匀分布中随机生成可逆CA。不幸的是，所产生的随机生成算法中的常数项太大而无法实际使用。我们表明，对于不那么普遍的零边界（NB）CA，这种常数可以大大降低，从而有利于统一随机生成的实用算法。我们的技术被进一步渐近地应用于计算可逆NBCA的数量。 （c）2007 Elsevier B.V.保留所有权利。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号