...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Automata, Languages and Combinatorics >CHURCH-ROSSER GROUPS AND GROWING CONTEXT-SENSITIVE GROUPS
【24h】

CHURCH-ROSSER GROUPS AND GROWING CONTEXT-SENSITIVE GROUPS

机译：传教士团体和成长中的上下文敏感团体

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

摘要

A finitely generated group is called a Church-Rosser group {growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.
机译：如果一个有限生成的组允许一个有限生成的表示形式，而该单词的问题是Church-Rosser（与上下文相关的成长型）语言，则该组称为Church-Rosser组（与上下文相关的成长型组）。尽管在集合包含条件下，Church-Rosser语言无法与上下文无关的语言相比，但它们严格包含确定性上下文无关的语言类别。由于每种无上下文的组语言实际上都是确定性的无上下文的语言，因此，所有无上下文的组都是Church-Rosser组。由于等级2的自由阿贝尔族群是非上下文无关的Church-Rosser族，因此这种包含是适当的。另一方面，我们表明，存在没有上下文无关的组，它们对上下文的敏感性不高。还为Church-Rosser和不断增长的上下文相关群体建立了一些封闭和非封闭属性。更一般地，我们还为Church-Rosser类和不断增长的上下文相关语言建立了一些新的特性和闭包属性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号