Published in Volume XXIX, Issue 1, 2019, pages 59–80, doi: 10.7561/SACS.2019.1.59
Authors: G. Rahonis, F. Torpari
Abstract
We introduce and investigate weighted context-free grammars over an arbitrary bimonoid K. Thus, we do not assume that the operations of K are commutative or idempotent or they distribute over each other. We prove a Chomsky-Schützenberger type theorem for the series generated by our grammars. Moreover, we show that the class of series generated by weighted right-linear grammars over a linearly ordered alphabet Σ and K coincides with that of recognizable series over Σ and K.
Full Text (PDF)References
[1] J.-M. Autebert, J. Berstel, L. Boasson. Context-Free Languages and Pushdown Automata. In G. Rozenberg, A. Salomaa (Eds.) Handbook of Formal Languages vol. 1, 111–174, Springer, 1997. doi:10.1007/978-3-642-59136-5.
[2] V. Bhattiprolu, S. Gordon, M. Viswanathan. Extending Parikhs Theorem to Weighted and Probabilistic Context-Free Grammars. In: N. Bertrand, L. Bortolussi (Eds.) Quantitative Evaluation of Systems (QEST 2017), Lecture Notes in Computer Science 10503, 3–19, 2017. doi:10.1007/978-3-319-66335-7_1.
[3] M.M. Bonsangue, J. Rutten, J. Winter. Defining Context-Free Power Series Coalgebraically. In D. Pattinson, L. Schrder (Eds.) Coalgebraic Methods in Computer Science (CMCS 2012), Lecture Notes in Computer Science 7399, 20–39, 2012. doi:10.1007/978-3-642-32784-1_2.
[4] M. Ćirić, M. Droste, J. Ignjatović, H. Vogler. Determinization of Weighted Finite Automata Over Strong Bimonoids. Information Sciences 180(18), 3497–3520, 2010. doi:10.1016/j.ins.2010.05.020.
[5] E.M. Clarke, O. Grumberg, S. Jha. Verifying Parameterized Networks Using Abstraction and Regular Languages. In I. Lee, S.A. Smolka (Eds.) Concurrency Theory (CONCUR 1995), Lecture Notes in Computer Science 962, 395–407, 1995. doi:10.1007/3-540-60218-6_30.
[6] M. Droste, W. Kuich. Semirings and Formal Power Series. Chapter 1 in [7]. doi:10.1007/978-3-642-01492-5_1.
[7] M. Droste, W. Kuich, H. Vogler (Eds.) Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin Heidelberg, 2009. doi:10.1007/978-3-642-01492-5.
[8] M. Droste, T. Kutsia, G. Rahonis, W. Schreiner. MK-Fuzzy Automata and MSO Logics. In P. Bouyer, A. Orlandini, P. San Pietro (Eds.) Proceedings Eighth International Symposium on Games, Automata, Logics and Formal Verification (GandALF 2017), Electronic Proceedings in Theoretical Computer Science 256, 106–120, 2917. doi:10.4204/EPTCS.256.8.
[9] M. Droste, T. Kutsia, G. Rahonis, W. Schreiner. MK-Fuzzy Automata and MSO Logics. Information and Computation, to appear.
[10] M. Droste, T. Stüber, H. Vogler, Weighted Finite Automata Over Strong Bimonoids. Information Sciences 180(1), 156–166, 2010. doi:10.1016/j.ins.2009.09.003.
[11] M. Droste, H. Vogler. The Chomsky-Schützenberger Theorem for Quantitative Context-Free Languages. International Journal of Foundations of Computer Science 25(8), 955–969, 2014. doi:10.1142/S0129054114400176.
[12] S. Eilenberg. Automata, Languages and Machines, vol. A. Academic Press, 1974.
[13] Z. Ésik, W. Kuich. Modern Automata Theory. Available at: http://www.dmg.tuwien.ac.at/kuich/mat.pdf.
[14] T. Hanneforth. A Practical Algorithm for Intersecting Weighted Context-Free Arammars. In Proceedings of 9th International Workshop on Finite State Methods and Natural Language Processing, 57–64, 2011, Association for Computational Linguistics.
[15] G. Hughes, T. Bultan. Interface Grammars for Modular Software Model Checking. In Proceedings of the 2007 International Symposium on Software Testing and Analysis (ISSTA 2007), ACM, 39–49, 2017. doi:10.1145/1273463.1273471.
[16] S. Kleene. Introduction to Metamathematics. North-Holland, 1952.
[17] D.C. Kozen. Automata and Computability. Spinger-Verlag, New York, 1997. doi:10.1007/978-1-4612-1844-9.
[18] W. Kuich, A. Salomaa. Semirings, Automata, Languages. EATCS Monographs in Theoretical Computer Science, Springer-Verlag, Berlin Heidelberg, 1986. doi:10.1007/978-3-642-69959-7.
[19] P. Li, Y. Li, S. Geng. The Realization Problems Related to Weighted Transducers Over Strong Bimonoids. In Proceedings of 2014 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE), 1686–1690, 2014. doi:10.1109/FUZZ-IEEE.2014.6891580.
[20] LogicGuard I. http://www.risc.jku.at/projects/LogicGuard/.
[21] LogicGuard II. http://www.risc.jku.at/projects/LogicGuard2/.
[22] J. McCarthy. A Basis for a Mathematical Theory of Computation, Computer Programming and Formal Systems. Studies in Logic and the Foundations of Mathematics 35, 33–70, 1963. doi:10.1016/S0049-237X(08)72018-4.
[23] P.O. Meredith, D. Jin, F. Chen, G. Roşu. Efficient Monitoring of Parametric Context-Free Patterns. Automated Software Engineering 17(2), 149–180, 2010. doi:10.1007/s10515-010-0063-y.
[24] J. Sakarovitch. Elements of Automata Theory. Cambridge University Press, 2009. doi:10.1017/CBO9781139195218.
[25] N.A. Smith, M. Johnson. Weighted and Probabilistic Context-Free Grammars are Equally Expressive. Computational Linguistics 33(4), 477–491, 2007. doi:10.1162/coli.2007.33.4.477.
[26] F. Torpari. Context-Free Series with Values in Bimonoids. Master Thesis, Aristotle University of Thessaloniki, Thessaloniki 2018. Available at: https://ikee.lib.auth.gr/record/299349/files/
FaidraTorpari.pdf.
[27] C. Yang, Y. Li. Bisimulation Relations for Weighted Automata Over Valuation Monoids. In T.H. Fan, S.L. Chen, S.M. Wang, Y.M. Li (Eds.) Proceedings of 4th International Conference on Quantitative Logic and Soft Computing (QLSC2016). Advances in Intelligent Systems and Computing 510, 181-191, 2016. doi:10.1007/978-3-319-46206-6_19.
[28] http://www.informatik.uni-leipzig.de/wata2018/.
Bibtex
@article{sacscuza:rahonis2019wcfgob,
title={Weighted Context-Free Grammars Over Bimonoids},
author={G. Rahonis, F. Torpari},
journal={Scientific Annals of Computer Science},
volume={29},
number={1},
organization={Alexandru Ioan Cuza University, Ia\c si, Rom\^ania},
year={2019},
pages={59–80},
publisher={Alexandru Ioan Cuza University Press, Ia\c si},
doi={10.7561/SACS.2019.1.59}
}