Omega-rational expressions with bounded synchronization delay
journal contribution
posted on 2018-02-23, 09:29 authored by Volker Diekert, Manfred Kufleitner© 2013, Springer Science+Business Media New York. In 1965 Sch ̈utzenberger published his famous result that star-free
languages (SF) and aperiodic languages (AP) coincide over finite words, often
written as SF = AP. Perrin generalized SF = AP to infinite words in the mid
1980s. In 1973 Sch ̈utzenberger presented another (and less known) characteri-
zation 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
SD. In this paper, we present a generalization of SD = AP to infinite words.
This became possible via a substantial simplification of the proof for the cor-
responding result for finite words. Moreover, we show that SD = AP can be
viewed as more fundamental than SF = AP in the sense that the classical 1965
result of Sch ̈utzenberger and its 1980s extension to infinite words by Perrin
are immediate consequences of SD = AP.
Funding
M.K. was supported by the German Research Foundation (DFG) under grant DI 435/5-1 and by ANR 2010 BLAN 0202 FREC.
History
School
- Science
Department
- Computer Science
Published in
Theory of Computing SystemsVolume
56Issue
4Pages
686 - 696Citation
DIEKERT, V. and KUFLEITNER, M., 2015. Omega-rational expressions with bounded synchronization delay. Theory of Computing Systems, 56(4), pp. 686-696.Publisher
© SpringerVersion
- AM (Accepted Manuscript)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/Publication date
2015Notes
This is a post-peer-review, pre-copyedit version of an article published in Theory of Computing Systems. The final authenticated version is available online at: https://doi.org/10.1007/s00224-013-9526-4ISSN
1432-4350eISSN
1433-0490Publisher version
Language
- en
Administrator link
Usage metrics
Categories
Keywords
Licence
Exports
RefWorksRefWorks
BibTeXBibTeX
Ref. managerRef. manager
EndnoteEndnote
DataCiteDataCite
NLMNLM
DCDC