On DR Tree Automata, Unary Algebras and Syntactic Path Monoids | Zendy

Magnus Steinby | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

On DR Tree Automata, Unary Algebras and Syntactic Path Monoids

Author(s) -

Magnus Steinby

Publication year - 2017

Publication title -

acta cybernetica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.143

H-Index - 18

eISSN - 2676-993X

pISSN - 0324-721X

DOI - 10.14232/actacyb.23.1.2017.10

Subject(s) - unary operation , tree (set theory) , mathematics , path (computing) , variety (cybernetics) , automaton , regular language , discrete mathematics , combinatorics , computer science , theoretical computer science , programming language , statistics

We consider deterministic root-to-frontier (DR) tree recognizers and the tree languages recognized by them from an algebraic point of view. We make use,of a correspondence between DR algebras and unary algebras shown by Z. Esik (1986). We also study a question raised by F. Gecseg (2007) that concerns the definability of families of DR-recognizable tree languages by syntactic path monoids. We show how the families of DR-recognizable tree languages path-definable by a variety of finite monoids (or semigroups) can be derived from varieties of string languages. In particular, the three path definable families of Gecseg and B. Imreh (2002, 2004) are obtained this way.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research