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 条
[41]   LIMITED AUTOMATA AND REGULAR LANGUAGES [J].
Pighizzini, Giovanni ;
Pisoni, Andrea .
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (07) :897-916
[42]   A TRICHOTOMY FOR REGULAR TRAIL QUERIES [J].
Martens, Wim ;
Niewerth, Matthias ;
Popp, Tina .
LOGICAL METHODS IN COMPUTER SCIENCE, 2023, 19 (04) :20:1-20:38
[43]   Syntactic structures of regular languages [J].
Klima, Ondrej ;
Polak, Libor .
THEORETICAL COMPUTER SCIENCE, 2019, 800 :125-141
[44]   A Trichotomy for Regular Trail Queries [J].
Martens, Wim ;
Niewerth, Matthias ;
Trautner, Tina .
37TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2020), 2020, 154
[45]   CATERPILLAR DUALITIES AND REGULAR LANGUAGES [J].
Erdos, Peter L. ;
Tardif, Claude ;
Tardos, Gabor .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (03) :1287-1294
[46]   Recognisability for algebras of infinite trees [J].
Blumensath, Achim .
THEORETICAL COMPUTER SCIENCE, 2011, 412 (29) :3463-3486
[47]   Complete Iterativity for Algebras with Effects [J].
Milius, Stefan ;
Palm, Thorsten ;
Schwencke, Daniel .
ALGEBRA AND COALGEBRA IN COMPUTER SCIENCE, PROCEEDINGS, 2009, 5728 :34-48
[48]   On semiflexible, flexible and pie algebras [J].
Bourke, John ;
Garner, Richard .
JOURNAL OF PURE AND APPLIED ALGEBRA, 2013, 217 (02) :293-321
[49]   Markov decision processes and regular events [J].
Courcoubetis, C ;
Yannakakis, M .
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1998, 43 (10) :1399-1418
[50]   A structural property of regular frequency computations [J].
Austinat, H ;
Diekert, V ;
Hertrampf, U .
THEORETICAL COMPUTER SCIENCE, 2003, 292 (01) :33-43
12345