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 条
[31]   Inferring regular languages and ω-languages [J].
Fisman, Dana .
JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING, 2018, 98 :27-49
[32]   Circuit Complexity of Regular Languages [J].
Koucky, Michal .
THEORY OF COMPUTING SYSTEMS, 2009, 45 (04) :865-879
[33]   Circuit complexity of regular languages [J].
Koucky, Michal .
COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS, 2007, 4497 :426-435
[34]   Circuit Complexity of Regular Languages [J].
Michal Koucký .
Theory of Computing Systems, 2009, 45 :865-879
[35]   On Decidability of Theories of Regular Languages [J].
Sergey Dudakov ;
Boris Karlov .
Theory of Computing Systems, 2021, 65 :462-478
[36]   On Decidability of Theories of Regular Languages [J].
Dudakov, Sergey ;
Karlov, Boris .
THEORY OF COMPUTING SYSTEMS, 2021, 65 (03) :462-478
[37]   On Decidability of Regular Languages Theories [J].
Dudakov, Sergey ;
Karlov, Boris .
COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2019, 11532 :119-130
[38]   On regular temporal logics with past [J].
Christian Dax ;
Felix Klaedtke ;
Martin Lange .
Acta Informatica, 2010, 47 :251-277
[39]   Regular closure of deterministic languages [J].
Bertsch, E ;
Nederhof, MJ .
SIAM JOURNAL ON COMPUTING, 1999, 29 (01) :81-102
[40]   Regular splicing languages and subclasses [J].
Bonizzoni, P ;
Mauri, G .
THEORETICAL COMPUTER SCIENCE, 2005, 340 (02) :349-363
12345