• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theoretical computer science >A characterization of regular circular languages generated by marked splicing systems
【24h】

A characterization of regular circular languages generated by marked splicing systems

机译：标记拼接系统生成的常规循环语言的特征

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

摘要

Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set I and a set R of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both I and R finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system S generates a regular circular language if and only if S satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages.
机译：剪接系统是形式语言的生成设备，由Head在1987年引入，用于对线性和圆形DNA分子上的生物现象进行建模。拼接系统是通过给出规则的初始集合I和集合R来定义的。一些未解决的问题与圆形拼接系统的计算能力有关。特别地，仍然有待解决的问题是找到由有限的圆形拼接系统（即，具有I和R个有限集的圆形拼接系统）产生的圆形语言的表征。在本文中，我们介绍了后者的一类特殊系统，称为标记系统。我们证明，只有当S满足特殊（可确定的）属性时，标记系统S才会生成规则的循环语言。结果，我们能够表征这些常规循环语言的结构。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号