Abstract
We show that an epsilon-free, chain-free synchronous context-free grammar (SCFG) can be converted into a weakly equivalent synchronous tree-adjoining grammar (STAG) which is prefix lexicalized. This transformation at most doubles the grammar’s rank and cubes its size, but we show that in practice the size increase is only quadratic. Our results extend Greibach normal form from CFGs to SCFGs and prove new formal properties about SCFG, a formalism with many applications in natural language processing.- Anthology ID:
- P18-1107
- Volume:
- Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)
- Month:
- July
- Year:
- 2018
- Address:
- Melbourne, Australia
- Editors:
- Iryna Gurevych, Yusuke Miyao
- Venue:
- ACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 1160–1170
- Language:
- URL:
- https://aclanthology.org/P18-1107
- DOI:
- 10.18653/v1/P18-1107
- Cite (ACL):
- Logan Born and Anoop Sarkar. 2018. Prefix Lexicalization of Synchronous CFGs using Synchronous TAG. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1160–1170, Melbourne, Australia. Association for Computational Linguistics.
- Cite (Informal):
- Prefix Lexicalization of Synchronous CFGs using Synchronous TAG (Born & Sarkar, ACL 2018)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-1/P18-1107.pdf