Synchronous context-free grammars and optimal linear parsing strategies

Pierluigi Crescenzi (1, 2) , Daniel Gildea (3) , Andrea Marino (4) , Gianluca Rossi (5) , Giorgio Satta (6)

1 UniFI - Università degli Studi di Firenze = University of Florence = Université de Florence
2 ERABLE - Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale
3 University of Rochester [USA]
4 ISLab - Dipartimento di Informatica
5 Università degli Studi di Roma Tor Vergata [Roma] = University of Rome Tor Vergata
6 DEI - Dipartimento di Ingegneria de l'Informazione [Padova]

Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata [1] and [2], are unlike context-free grammars in that they do not have a binary normal form. In general, parsing with SCFGs takes space and time polynomial in the length of the input strings, but with the degree of the polynomial depending on the permutations of the SCFG rules. We consider linear parsing strategies, which add one nonterminal at a time. We show that for a given input permutation, the problems of finding the linear parsing strategy with the minimum space and time complexity are both NP-hard.

Domaines: Algorithme et structure de données [cs.DS]

Pierluigi Crescenzi, Daniel Gildea, Andrea Marino, Gianluca Rossi, Giorgio Satta. Synchronous context-free grammars and optimal linear parsing strategies. Journal of Computer and System Sciences, 2015, 81 (7), pp.1333-1356. ⟨10.1016/j.jcss.2015.04.003⟩. ⟨hal-01249108⟩