On DR tree automata, unary algebras and syntactic path monoids

Steinby Magnus: On DR tree automata, unary algebras and syntactic path monoids. In: Acta cybernetica, (23) 1. pp. 159-174. (2017)

[thumbnail of actacyb_23_1_2017_10.pdf]
Cikk, tanulmány, mű

Download (373kB) | Preview


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. Gécseg (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 pathdefinable families of Gécseg and B. Imreh (2002, 2004) are obtained this way.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2017
Volume: 23
Number: 1
ISSN: 0324-721X
Page Range: pp. 159-174
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/50021/
DOI: 10.14232/actacyb.23.1.2017.10
Uncontrolled Keywords: Algebrai struktúra, Matematikai nyelvészet - számítógépes nyelvészet, Automaták elmélete
Additional Information: Bibliogr.: p. 173-174. és a lábjegyzetekben ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.01. Mathematics
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2018. Feb. 12. 09:28
Last Modified: 2022. Jun. 20. 15:37
URI: http://acta.bibl.u-szeged.hu/id/eprint/50068

Actions (login required)

View Item View Item