...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Theoretical computer science >Complementation of rational sets on scattered linear orderings of finite rank
【24h】

Complementation of rational sets on scattered linear orderings of finite rank

机译：有限秩的离散线性有序集的有理补集

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

摘要

In a preceding paper [V. Bruyere, O. Carton, Automata on linear orderings, in: J. Sgall, A. Pultr, P. Kolman (Eds.), MFCS’2001, in: Lect. Notes in Comput. Sci., vol. 2136, 2001, pp. 236–247. iGM report 2001-12], automata have been introduced for words indexed by linear orderings. These automata are a generalization of automata for finite, infinite, bi-infinite, and even transfinite words studied by Büchi. Kleene’s theorem has been generalized to these words. We show that deterministic automata do not have the same expressive power. Despite this negative result, we prove that rational sets of words of finite ranks are closed under complementation.
机译：在先前的论文中[V. Bruyere，O。Carton，关于线性排序的自动机，在：J. Sgall，A。Pultr，P。Kolman（编辑），MFCS’2001，在：Lect。计算中的注释。科学，卷。 2136，2001，第236-247页。 [iGM报告2001-12]，已经为线性排序索引的单词引入了自动机。这些自动机是Büchi研究的有限，无限，双无限甚至超限单词自动机的一般化。克莱因定理已推广到这些词。我们证明确定性自动机不具有相同的表达能力。尽管有这个负面结果，我们证明有限等级的有理词集在补码下是封闭的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号