Prefix Lexicalization of Synchronous CFGs using Synchronous TAG

Logan Born, Anoop Sarkar


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
Bibkey:
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)
Copy Citation:
PDF:
https://aclanthology.org/P18-1107.pdf
Note:
 P18-1107.Notes.pdf
Video:
 https://aclanthology.org/P18-1107.mp4