Synchronous forest substitution grammars

Maletti Andreas: Synchronous forest substitution grammars. In: Acta cybernetica, (23) 1. pp. 269-281. (2017)

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

Download (391kB) | Preview


The expressive power of synchronous forest (tree-sequence) substitution grammars (SFSGs) is studied in relation to multi bottom-up tree transducers (MBOTs). It is proved that SFSGs have exactly the same expressive power as compositions of an inverse MBOT with an MBOT. This result is used to derive complexity results for SFSGs and the fact that compositions of an MBOT with an inverse MBOT can compute tree translations that cannot be computed by any SFSG, although the class of tree translations computable by MBOTs is closed under composition.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2017
Volume: 23
Number: 1
ISSN: 0324-721X
Page Range: pp. 269-281
Language: English
Place of Publication: Szeged
Related URLs:
DOI: 10.14232/actacyb.23.1.2017.15
Uncontrolled Keywords: Matematikai nyelvészet - számítógépes nyelvészet
Additional Information: Bibliogr.: p. 280-281. ; ö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. 14:28
Last Modified: 2022. Jun. 20. 15:25

Actions (login required)

View Item View Item