Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata [1,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. (C) 2015 Elsevier Inc. All rights reserved.

Crescenzi, P., Gildea, D., Marino, A., Rossi, G., Satta, G. (2015). Synchronous context-free grammars and optimal linear parsing strategies. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), 1333-1356 [10.1016/j.jcss.2015.04.003].

Synchronous context-free grammars and optimal linear parsing strategies

ROSSI, GIANLUCA;
2015-01-01

Abstract

Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata [1,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. (C) 2015 Elsevier Inc. All rights reserved.
2015
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
English
Crescenzi, P., Gildea, D., Marino, A., Rossi, G., Satta, G. (2015). Synchronous context-free grammars and optimal linear parsing strategies. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 81(7), 1333-1356 [10.1016/j.jcss.2015.04.003].
Crescenzi, P; Gildea, D; Marino, A; Rossi, G; Satta, G
Articolo su rivista
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/133706
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact