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...
Elmentve itt :
| Szerző: | |
|---|---|
| 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 |