REGULAR TREE ALGEBRAS

被引：3
作者：
Blumensath, Achim [1 ]
机构：
[1] Masaryk Univ Brno, Brno, Czech Republic
来源：
LOGICAL METHODS IN COMPUTER SCIENCE | 2020年 / 16卷 / 01期
关键词：
infinite trees; tree algebras; regular languages; monads;
D O I：
10.23638/LMCS-16(1:16)2020
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We introduce a class of algebras that can be used as recognisers for regular tree languages. We show that it is the only such class that forms a pseudo-variety and we prove the existence of syntactic algebras. Finally, we give a more algebraic characterisation of the algebras in our class.
引用
收藏
页数：25
相关论文
共 50 条
[21]   On the Density of Regular Languages [J].
Koga, Toshihiro .
FUNDAMENTA INFORMATICAE, 2019, 168 (01) :45-49
[22]   IT IS NL-COMPLETE TO DECIDE WHETHER A HAIRPIN COMPLETION OF REGULAR LANGUAGES IS REGULAR [J].
Diekert, Volker ;
Kopecki, Steffen .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2011, 22 (08) :1813-1828
[23]   A note on algebras of languages [J].
Marini, Claudio ;
Simi, Giulia ;
Sorbi, Andrea ;
Sorrentino, Marianna .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (46) :6531-6536
[24]   ASPECTS OF ALGEBRAIC ALGEBRAS [J].
Hofmann, Dirk ;
Sousa, Lurdes .
LOGICAL METHODS IN COMPUTER SCIENCE, 2017, 13 (03)
[25]   Bilinear factorization of algebras [J].
Boehm, Gabriella ;
Gomez-Torrecillas, Jose .
BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 2013, 20 (02) :221-244
[26]   Parameterized Regular Expressions and Their Languages [J].
Barcelo, Pablo ;
Libkin, Leonid ;
Reutter, Juan L. .
IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2011), 2011, 13 :351-362
[27]   Reversal of binary regular languages [J].
Jiraskova, Galina ;
Sebej, Juraj .
THEORETICAL COMPUTER SCIENCE, 2012, 449 :85-92
[28]   Derivatives for Enhanced Regular Expressions [J].
Thiemann, Peter .
IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2016, 9705 :285-297
[29]   A pumping condition for regular sets [J].
Varricchio, S .
SIAM JOURNAL ON COMPUTING, 1997, 26 (03) :764-771
[30]   The pseudopalindromic completion of regular languages [J].
Fazekas, Szilard Zsolt ;
Manea, Florin ;
Mercas, Robert ;
Shikishima-Tsuji, Kayoko .
INFORMATION AND COMPUTATION, 2014, 239 :222-236
12345