• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Descriptional Complexity of Formal Systems >Nondeterministic Right One-Way Jumping Finite Automata (Extended Abstract)
【24h】

Nondeterministic Right One-Way Jumping Finite Automata (Extended Abstract)

机译：非确定性权利单向跳跃有限自动机（扩展摘要）

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

摘要

Right one-way jumping finite automata are deterministic devices that process their input in a discontinuous fashion. We generalise these devices to nondeterministic machines. More precisely we study the impact on the computational power of these machines when allowing multiple initial states and/or a nondeterministic transition function including spontaneous or A-transitions. We show inclusion relations and incomparability results of the induced language families. Since for right-one way jumping devices the use of spontaneous transitions is subject to different natural interpretations, we also study this subject in detail, showing that most interpretations are equivalent to each other and lead to the same language families. Finally we also study inclusion and incomparability results to classical language families and to the families of languages accepted by finite automata with translucent letters.
机译：正确的单向跳跃有限自动机是确定性设备，可以以不连续的方式处理其输入。我们将这些设备推广到不确定性机器上。更准确地说，当允许多个初始状态和/或不确定的转换函数（包括自发或A转换）时，我们研究对这些机器的计算能力的影响。我们显示了归纳语言族的包含关系和不可比性结果。由于对于单向跳跃设备，自发过渡的使用受不同的自然解释的约束，因此我们也对此主题进行了详细研究，表明大多数解释是彼此等同的，并导致相同的语言家族。最后，我们还研究了包含和不兼容结果对古典语言家族和半透明字母的有限自动机接受的语言家族的影响。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号