An ambiguity hierarchy of weighted context-free grammars. (English) Zbl 07739132
Summary: Weighted context-free grammar (WCFG) is a quantitative extension of context-free grammar (CFG). It is known that unambiguous weighted automata (WA), finitely-ambiguous WA, polynomially-ambiguous WA and general WA over the tropical semiring have different expressive powers. We prove that there exists a similar ambiguity hierarchy of WCFG over the tropical semiring, using an extended Ogden’s lemma. In addition, we prove that each of the classes of finitely-ambiguous, polynomially-ambiguous, and exponentially-ambiguous WCFG can be subdivided into a finer strict hierarchy. We further show that the hierarchy we proved is different from the known ambiguity hierarchy of unweighted CFG.
MSC:
| 68Qxx | Theory of computing |
References:
| [1] | Chattopadhyay, A.; Mazowiecki, F.; Muscholl, A.; Riveros, C., Pumping lemmas for weighted automata (2020), CoRR |
| [2] | Chomsky, N.; Schützenberger, M. P., The Algebraic Theory of Context-free Languages, Studies in Logic and the Foundations of Mathematics, vol. 26, 118-161 (1959) · Zbl 0148.00804 |
| [3] | Droste, M.; Kuich, W.; Vogler, H., Handbook of Weighted Automata (2009), Springer Science & Business Media · Zbl 1200.68001 |
| [4] | Durbin, R.; Eddy, S. R.; Krogh, A.; Mitchison, G., Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids (1998), Cambridge University Press · Zbl 0929.92010 |
| [5] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley · Zbl 0426.68001 |
| [6] | Inoue, Y.; Hashimoto, K.; Seki, H., An ambiguity hierarchy of weighted context-free grammars, (26th International Conference on Implementation and Application of Automata. 26th International Conference on Implementation and Application of Automata, CIAA 2022 (2022)), 238-250 · Zbl 07572326 |
| [7] | Lari, K.; Young, S. J., The estimation of stochastic context-free grammars using the inside-outside algorithm, Comput. Speech Lang., 4, 1, 35-56 (1990) |
| [8] | Lari, K.; Young, S. J., Applications of stochastic context-free grammars using the inside-outside algorithm, Comput. Speech Lang., 5, 3, 237-257 (1991) |
| [9] | Maletti, A., Survey: finite-state technology in natural language processing, Theor. Comput. Sci., 679, 2-17 (2017) · Zbl 1373.68420 |
| [10] | Maletti, A.; Nasz, T.; Stier, K.; Ulbriht, M., Ambiguity hierarchies for weighted tree automata, (25th International Conference on Implementation and Application of Automata. 25th International Conference on Implementation and Application of Automata, CIAA 2021 (2021)), 140-151 · Zbl 07495111 |
| [11] | Mazowiecki, F.; Riveros, C., Pumping lemmas for weighted automata, (35th International Symposium on Theoretical Aspects of Computer Science. 35th International Symposium on Theoretical Aspects of Computer Science, STACS 2018 (2018)), 50:1-50:14 · Zbl 1487.68151 |
| [12] | Ogden, W., A helpful result for proving inherent ambiguity, Math. Syst. Theory, 2, 3, 191-194 (1968) · Zbl 0175.27802 |
| [13] | Wich, K., Exponential ambiguity of context-free grammars, (4th International Conference on Developments in Language Theory. 4th International Conference on Developments in Language Theory, DLT 1999 (1999)), 125-138 · Zbl 1013.68098 |
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.
