A1 Refereed original research article in a scientific journal
On DR Tree Automata, Unary Algebras and Syntactic Path Monoids
Authors: Magnus Steinby
Publisher: UNIV SZEGED, FAC SCIENCE
Publication year: 2017
Journal: Acta Cybernetica
Journal name in source: ACTA CYBERNETICA
Journal acronym: ACTA CYBERN
Volume: 23
Issue: 1
First page : 159
Last page: 174
Number of pages: 16
ISSN: 0324-721X
DOI: https://doi.org/10.14232/actacyb.23.1.2017.10
Abstract
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.
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.
UTU Research Portal