Regular expressions for muller context-free languages

被引：0
作者：
Gelle K. [1 ]
Ivan S. [1 ]
机构：
[1] University of Szeged, Szeged
来源：
Acta Cybernetica | 2017年 / 23卷 / 01期
关键词：
Muller context-free languages; regular expressions; well-ordered induction;
D O I：
10.14232/actacyb.23.1.2017.19
中图分类号：
学科分类号：
摘要：
Muller context-free languages (MCFLs) are languages of countable words, that is, labeled countable linear orders, generated by Muller context-free grammars. Equivalently, they are the frontier languages of (nondeterministic Muller-)regular languages of infinite trees. In this article we survey the known results regarding MCFLs, and show that a language is an MCFL if and only if it can be generated by a so-called μ η-regular expression.
引用
收藏
页码：349 / 369
页数：20
相关论文
共 25 条
[1]  
Bedon N., Finite automata and ordinals, Theor. Comput. Sci., 156, 1-2, pp. 119-144, (1996)
[2]  
Bedon N., Bes A., Carton O., Rispal C., Logic and Ra- Tional Languages of Words Indexed by Linear Orderings, pp. 76-85, (2008)
[3]  
Boasson L., Context-free sets of infinite words, Theoretical Computer Science, Volume 67 of Lecture Notes in Computer Science, pp. 1-9, (1979)
[4]  
Bruyere V., Carton O., Automata on linear orderings, J. Comput. Syst. Sci., 73, 1, pp. 1-24, (2007)
[5]  
Bes A., Carton O., A Kleene theorem for languages of words indexed by linear orderings, Developments in Language Theory, Volume 3572 of Lecture Notes in Computer Science, pp. 158-167, (2005)
[6]  
Buchi J.R., The Monadic Second Order Theory of ω1, pp. 1-127, (1973)
[7]  
Choueka Y., Finite automata, definable sets, and regular expressions over ωn-tapes, Journal of Computer and System Sciences, 17, 1, pp. 81-97, (1978)
[8]  
Cohen R.S., Gold A.Y., Theory of ω-languages. I. Characterizations of ω-context-free languages, J. Comput. Syst. Sci., 15, 2, pp. 169-184, (1977)
[9]  
Courcelle B., Frontiers of infinite trees, ITA, 12, 4, (1978)
[10]  
Esik Z., Ivan S., Büchi context-free languages, Theor. Comput. Sci., 412, 8-10, pp. 805-821, (2011)
123