Abstract
The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of a context-free grammar (CFG) or pushdown automaton (PDA) controlling another CFG or PDA. These four formalisms are equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG), pushdown-adjoining automata (PAA), and embedded pushdown automata (EPDA). We define semiring-weighted versions of the above two-level formalisms, and we design new algorithms for computing their stringsums (the weight of all derivations of a string) and allsums (the weight of all derivations). From these, we also immediately obtain stringsum and allsum algorithms for TAG, LIG, PAA, and EPDA. For LIG, our algorithm is more time-efficient by a factor of πͺ(n|π©|) (where n is the string length and |π©| is the size of the nonterminal set) and more space-efficient by a factor of πͺ(|π€|) (where π€ is the size of the stack alphabet) than the algorithm of Vijay-Shanker and Weir (1989). For EPDA, our algorithm is both more space-efficient and time-efficient than the algorithm of Alonso et al. (2001) by factors of πͺ(|π€|2) and πͺ(|π€|3), respectively. Finally, we give the first PAA stringsum and allsum algorithms.- Anthology ID:
- 2023.emnlp-main.328
- Volume:
- Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing
- Month:
- December
- Year:
- 2023
- Address:
- Singapore
- Editors:
- Houda Bouamor, Juan Pino, Kalika Bali
- Venue:
- EMNLP
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 5394β5416
- Language:
- URL:
- https://aclanthology.org/2023.emnlp-main.328
- DOI:
- 10.18653/v1/2023.emnlp-main.328
- Cite (ACL):
- Alexandra Butoi, Tim Vieira, Ryan Cotterell, and David Chiang. 2023. Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5394β5416, Singapore. Association for Computational Linguistics.
- Cite (Informal):
- Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages (Butoi et al., EMNLP 2023)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-2/2023.emnlp-main.328.pdf