Synchronous context-free grammars and optimal linear parsing strategies. (English) Zbl 1320.68106
Summary: Synchronous Context-Free Grammars (SCFGs), also known as syntax-directed translation schemata, 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.
MSC:
| 68Q42 | Grammars and rewriting systems |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q45 | Formal languages and automata |
References:
| [1] | Aho, A. V.; Ullman, J. D., Syntax directed translations and the pushdown assembler, J. Comput. Syst. Sci., 3, 37-56 (1969) · Zbl 0182.02003 |
| [2] | Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation, and Compiling, vol. 1 (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0264.68032 |
| [3] | Lewis, P. M.; Stearns, R. E., Syntax-directed transduction, J. ACM, 15, 3, 465-488 (1968) · Zbl 0164.32102 |
| [4] | Shieber, S.; Schabes, Y., Synchronous tree-adjoining grammars, (Proceedings of the 13th International Conference on Computational Linguistics. Proceedings of the 13th International Conference on Computational Linguistics, COLING-90, Helsinki, vol. III (1990)), 253-258 |
| [5] | Schabes, Y.; Shieber, S. M., An alternative conception of tree-adjoining derivation, Comput. Linguist., 20, 91-124 (1994) |
| [6] | Chiang, D., Evaluation of grammar formalisms for applications to natural language processing and biological sequence analysis (2004), University of Pennsylvania, Ph.D. thesis |
| [7] | Chiang, D., Hierarchical phrase-based translation, Comput. Linguist., 33, 2, 201-228 (2007) · Zbl 1234.68401 |
| [8] | Galley, M.; Hopkins, M.; Knight, K.; Marcu, D., What’s in a translation rule?, (Proceedings of the 2004 Meeting of the North American Chapter of the Association for Computational Linguistics. Proceedings of the 2004 Meeting of the North American Chapter of the Association for Computational Linguistics, NAACL-04, Boston (2004)), 273-280 |
| [9] | Brown, P. F.; Della Pietra, S. A.; Della Pietra, V. J.; Mercer, R. L., The mathematics of statistical machine translation: parameter estimation, Comput. Linguist., 19, 2, 263-311 (1993) |
| [10] | Koehn, P.; Och, F. J.; Marcu, D., Statistical phrase-based translation, (Proceedings of the 2003 Meeting of the North American Chapter of the Association for Computational Linguistics. Proceedings of the 2003 Meeting of the North American Chapter of the Association for Computational Linguistics, NAACL-03, Edmonton, Alberta (2003)), 48-54 |
| [11] | Younger, D. H., Recognition and parsing of context-free languages in time \(n^3\), Inf. Control, 10, 189-208 (1967) · Zbl 0149.24803 |
| [12] | Earley, J., An efficient context-free parsing algorithm, Commun. ACM, 6, 8, 451-455 (1970) · Zbl 0185.43401 |
| [13] | Satta, G.; Peserico, E., Some computational complexity results for synchronous context-free grammars, (Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing. Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, HLT/EMNLP, Vancouver, Canada (2005)), 803-810 |
| [14] | Gildea, D.; Štefankovič, D., Worst-case synchronous grammar rules, (Proceedings of the 2007 Meeting of the North American Chapter of the Association for Computational Linguistics. Proceedings of the 2007 Meeting of the North American Chapter of the Association for Computational Linguistics, NAACL-07 (2007)), 147-154 |
| [15] | Huang, L.; Zhang, H.; Gildea, D.; Knight, K., Binarization of synchronous context-free grammars, Comput. Linguist., 35, 4, 559-595 (2009) |
| [16] | Crescenzi, P.; Gildea, D.; Marino, A.; Rossi, G.; Satta, G., Optimal head-driven parsing complexity for linear context-free rewriting systems, (Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, ACL-11 (2011)), 450-459 |
| [17] | Gómez-Rodríguez, C.; Kuhlmann, M.; Satta, G.; Weir, D., Optimal reduction of rule length in Linear context-free rewriting systems, (Proceedings of the 2009 Meeting of the North American Chapter of the Association for Computational Linguistics. Proceedings of the 2009 Meeting of the North American Chapter of the Association for Computational Linguistics, NAACL-09 (2009)), 539-547 |
| [18] | Sagot, B.; Satta, G., Optimal rank reduction for linear context-free rewriting systems with fan-out two, (Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, Uppsala, Sweden (2010)), 525-533 |
| [19] | Gómez-Rodríguez, C.; Kuhlmann, M.; Satta, G., Efficient parsing of well-nested linear context-free rewriting systems, (Human Language Technologies: the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Human Language Technologies: the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Los Angeles, California (2010)), 276-284 |
| [20] | Vijay-Shankar, K.; Weir, D. L.; Joshi, A. K., Characterizing structural descriptions produced by various grammatical formalisms, (Proceedings of the 25th Annual Conference of the Association for Computational Linguistics. Proceedings of the 25th Annual Conference of the Association for Computational Linguistics, ACL-87, Stanford, CA (1987)), 104-111 |
| [21] | Seki, H.; Matsumura, T.; Fujii, M.; Kasami, T., On multiple context-free grammars, Theor. Comput. Sci., 88, 191-229 (1991) · Zbl 0762.68039 |
| [22] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 |
| [23] | Bui, T.; Chaudhuri, S.; Leighton, T.; Sipser, M., Graph bisection algorithms with good average case behavior, Combinatorica, 7, 171-191 (1987) |
| [24] | Makedon, F.; Papadimitriou, C.; Sudborough, I., Topological bandwidth, SIAM J. Algebr. Discrete Methods, 6, 418-444 (1985) · Zbl 0573.05052 |
| [25] | Rolim, J. D.P.; Sýkora, O.; Vrto, I., Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes, (21st International Workshop on Graph-Theoretic Concepts in Computer Science (1995)), 252-264 · Zbl 1533.68267 |
| [26] | Gildea, D., Grammar factorization by tree decomposition, Comput. Linguist., 37, 1, 231-248 (2011) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
