首页> 外文期刊>International Journal of Foundations of Computer Science >Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation
【24h】

Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation

机译:在明星和互补下由前缀,后缀,因子和序列语言生成的Kuratowski代数

获取原文
获取原文并翻译 | 示例

摘要

We study Kuratowski algebras generated by prefix-, suffix-, factor-, and subword-free languages under the operations of star and complementation. We examine 12 possible algebras, and for each of them, we decide whether or not it can be generated by a prefix-, suffix-, factor-, or subword-free language. In each case when an algebra can be generated by such a language, we show that this language can be taken to be regular, and we compute upper bounds on the state complexities of all the generated languages. Finally, we find generators that maximize these complexities.
机译:我们研究了明星和互补的操作下的前缀,后缀,因子和序列语语言生成的Kuratowski代数。 我们检查12种可能的代数,以及每个可能的代数,我们决定它是否可以由前缀,后缀,因子或自行语中生成。 在每种情况下,当代数可以通过这样的语言生成时,我们表明这种语言可以是常规的,并且我们计算所有生成语言的状态复杂性上的上限。 最后,我们发现了最大化这些复杂性的生成器。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号