Maletti Andreas: Synchronous forest substitution grammars. In: Acta cybernetica, (23) 1. pp. 269-281. (2017)
Preview |
Cikk, tanulmány, mű
actacyb_23_1_2017_15.pdf Download (391kB) | Preview |
Abstract
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: | http://acta.bibl.u-szeged.hu/50021/ |
| 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 |
| URI: | http://acta.bibl.u-szeged.hu/id/eprint/50073 |
Actions (login required)
 |
View Item |
