Omega-Rational Expressions with Bounded Synchronization Delay
Omega-Rational Expressions with Bounded Synchronization Delay
复制标题
具有有限同步延迟的 Omega-Rational 表达式
DOI：
10.1007/s00224-013-9526-4
复制
发表时间：
2015
影响因子：
0.5
通讯作者：
M. Kufleitner
中科院分区：
文献类型：
--
作者：
V. Diekert;M. Kufleitner
1965年sch<s:1>岑伯格发表了他著名的结果，无星语言（）和非周期语言（）在有限的单词上重合，通常写成。佩林在20世纪80年代中期将其推广到无限词。1973年sch<s:1>岑伯格提出了另一种（不太为人所知的）非周期语言的有理式表征，其中星形运算的使用仅限于具有有限同步延迟的前缀码，并且不使用互补。这类语言我们用。在本文中，我们给出了对无限词的推广。这是通过对有限词的相应结果的证明进行实质性的简化而成为可能的。此外，我们表明，这可以被视为更基本的意义上，1965年sch<s:1>岑伯格的经典结果和1980年代Perrin对无限单词的扩展是直接后果。
In 1965 Schützenberger published his famous result that star-free languages () and aperiodic languages () coincide over finite words, often written as. Perrin generalizedto infinite words in the mid 1980s. In 1973 Schützenberger presented another (and less known) characterization of aperiodic languages in terms of rational expressions where the use of the star operation is restricted to prefix codes with bounded synchronization delay and no complementation is used. We denote this class of languages by. In this paper, we present a generalization ofto infinite words. This became possible via a substantial simplification of the proof for the corresponding result for finite words. Moreover, we show thatcan be viewed as more fundamental thanin the sense that the classical 1965 result of Schützenberger and its 1980s extension to infinite words by Perrin are immediate consequences of.
登录
查看更多内容
对于 Mazurkiewicz 轨迹来说，纯粹的未来局部时序逻辑是表达完整的
DOI：
10.1016/j.ic.2006.07.002
发表时间：
2004
期刊：
Inf. Comput.
影响因子：
--
作者：
V. Diekert;P. Gastin
通讯作者：
P. Gastin
无计数器自动机（麻省理工学院研究专着第 65 号）
影响因子：
0.7
作者：
R. McNaughton;S. Papert
通讯作者：
S. Papert
自动机和无限词的最新结果
DOI：
--
发表时间：
1984
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
D. Perrin
通讯作者：
D. Perrin
DOI：
10.5117/9789053565766
发表时间：
2007
期刊：
--
影响因子：
--
作者：
J. Flum;E. Grädel;T. Wilke
通讯作者：
J. Flum;E. Grädel;T. Wilke
局部琐碎的类别和明确的串联
DOI：
--
发表时间：
1988
期刊：
影响因子：
--
作者：
J. Pin;Howard Straubing;D. Thérien
通讯作者：
D. Thérien