A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On DR Tree Automata, Unary Algebras and Syntactic Path Monoids
Tekijät: Magnus Steinby
Kustantaja: UNIV SZEGED, FAC SCIENCE
Julkaisuvuosi: 2017
Journal: Acta Cybernetica
Tietokannassa oleva lehden nimi: ACTA CYBERNETICA
Lehden akronyymi: ACTA CYBERN
Vuosikerta: 23
Numero: 1
Aloitussivu: 159
Lopetussivu: 174
Sivujen määrä: 16
ISSN: 0324-721X
DOI: https://doi.org/10.14232/actacyb.23.1.2017.10
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali