Synchronous forest substitution grammars

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 c...

Teljes leírás

Elmentve itt :
Bibliográfiai részletek
Szerző: Maletti Andreas
Dokumentumtípus: Cikk
Megjelent: 2017
Sorozat:Acta cybernetica 23 No. 1
Kulcsszavak:Matematikai nyelvészet - számítógépes nyelvészet
Tárgyszavak:
doi:10.14232/actacyb.23.1.2017.15

Online Access:http://acta.bibl.u-szeged.hu/50073
LEADER 01366nab a2200241 i 4500
001 acta50073
005 20220620152538.0
008 180212s2017 hu o 0|| eng d
022 |a 0324-721X 
024 7 |a 10.14232/actacyb.23.1.2017.15  |2 doi 
040 |a SZTE Egyetemi Kiadványok Repozitórium  |b hun 
041 |a eng 
100 1 |a Maletti Andreas 
245 1 0 |a Synchronous forest substitution grammars  |h [elektronikus dokumentum] /  |c  Maletti Andreas 
260 |c 2017 
300 |a 269-281 
490 0 |a Acta cybernetica  |v 23 No. 1 
520 3 |a 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. 
650 4 |a Természettudományok 
650 4 |a Matematika 
650 4 |a Számítás- és információtudomány 
695 |a Matematikai nyelvészet - számítógépes nyelvészet 
856 4 0 |u http://acta.bibl.u-szeged.hu/50073/1/actacyb_23_1_2017_15.pdf  |z Dokumentum-elérés