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]
Előnézet
Cikk, tanulmány, mű
actacyb_23_1_2017_15.pdf

Letöltés (391kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 2017
Kötet: 23
Szám: 1
ISSN: 0324-721X
Oldalak: pp. 269-281
Nyelv: angol
Kiadás helye: Szeged
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/50021/
DOI: 10.14232/actacyb.23.1.2017.15
Kulcsszavak: Matematikai nyelvészet - számítógépes nyelvészet
Megjegyzések: Bibliogr.: p. 280-281. ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.01. Matematika
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2018. feb. 12. 14:28
Utolsó módosítás: 2022. jún. 20. 15:25
URI: http://acta.bibl.u-szeged.hu/id/eprint/50073
Bővebben:
Tétel nézet Tétel nézet