Document Open Access Logo

Weighted Operator Precedence Languages

Authors Manfred Droste, Stefan Dück, Dino Mandrioli, Matteo Pradella

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.31.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Manfred Droste
Stefan Dück
Dino Mandrioli
Matteo Pradella

Cite As Get BibTex

Manfred Droste, Stefan Dück, Dino Mandrioli, and Matteo Pradella. Weighted Operator Precedence Languages. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.31

Abstract

In the last years renewed investigation of operator precedence languages (OPL) led to discover important properties thereof: OPL are closed with respect to all major operations, are characterized, besides the original grammar family, in terms of an automata family (OPA) and an MSO logic; furthermore they significantly generalize the well-known visibly pushdown languages (VPL). In another area of research, quantitative models of systems are also greatly in demand. In this paper, we lay the foundation to marry these two research fields. We introduce weighted operator precedence automata and show how they are both strict extensions of OPA and weighted visibly pushdown automata. We prove a Nivat-like result which shows that quantitative OPL can be described by unweighted OPA and very particular weighted OPA. In a Büchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.

Subject Classification

Keywords
  • Quantitative automata
  • operator precedence languages
  • input-driven languages
  • visibly pushdown languages
  • quantitative logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur and Dana Fisman. Colored nested words. In Adrian Horia Dediu, Jan Janousek, Carlos Martín-Vide, and Bianca Truthe, editors, Language and Automata Theory and Applications, LATA 2016, volume 9618 of LNCS, pages 143-155. Springer, 2016. Google Scholar
  2. Rajeev Alur and Parthasarathy Madhusudan. Adding nesting structure to words. J. ACM, 56(3):16:1-16:43, 2009. Google Scholar
  3. Alessandro Barenghi, Stefano Crespi Reghizzi, Dino Mandrioli, Federica Panella, and Matteo Pradella. Parallel parsing made practical. Sci. Comput. Program., 112(3):195-226, 2015. URL: http://dx.doi.org/10.1016/j.scico.2015.09.002.
  4. Jean Berstel and Christophe Reutenauer. Rational Series and Their Languages, volume 12 of EATCS Monographs in Theoretical Computer Science. Springer, 1988. Google Scholar
  5. Benedikt Bollig and Paul Gastin. Weighted versus probabilistic logics. In Volker Diekert and Dirk Nowotka, editors, Developments in Language Theory, DLT 2009, volume 5583 of LNCS, pages 18-38. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-02737-6_2.
  6. J. Richard Büchi. Weak second-order arithmetic and finite automata. Z. Math. Logik und Grundlagen Math., 6:66-92, 1960. Google Scholar
  7. Christian Choffrut, Andreas Malcher, Carlo Mereghetti, and Beatrice Palano. First-order logics: some characterizations and closure properties. Acta Inf., 49(4):225-248, 2012. Google Scholar
  8. Stefano Crespi Reghizzi and Dino Mandrioli. Operator precedence and the visibly pushdown property. J. Comput. Syst. Sci., 78(6):1837-1867, 2012. Google Scholar
  9. Manfred Droste and Stefan Dück. Weighted automata and logics for infinite nested words. Inf. Comput., 253:448-466, 2017. URL: http://dx.doi.org/10.1016/j.ic.2016.06.010.
  10. Manfred Droste, Stefan Dück, Dino Mandrioli, and Matteo Pradella. Weighted operator precedence languages. CoRR, abs/1702.04597, 2017. URL: http://arXiv.org/abs/1702.04597.
  11. Manfred Droste and Paul Gastin. Weighted automata and weighted logics. Theor. Comput. Sci., 380(1-2):69-86, 2007. extended abstract in ICALP 2005. URL: http://dx.doi.org/10.1016/j.tcs.2007.02.055.
  12. Manfred Droste, Doreen Heusel, and Heiko Vogler. Weighted unranked tree automata over tree valuation monoids and their characterization by weighted logics. In Andreas Maletti, editor, Conference Algebraic Informatics CAI 2015, volume 9270 of LNCS, pages 90-102. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-23021-4_9.
  13. Manfred Droste, Werner Kuich, and Heiko Vogler, editors. Handbook of Weighted Automata. EATCS Monographs in Theoretical Computer Science. Springer, 2009. Google Scholar
  14. Manfred Droste and Ingmar Meinecke. Weighted automata and weighted MSO logics for average and long-time behaviors. Inf. Comput., 220:44-59, 2012. URL: http://dx.doi.org/10.1016/j.ic.2012.10.001.
  15. Manfred Droste and Bundit Pibaljommee. Weighted nested word automata and logics over strong bimonoids. Int. J. Found. Comput. Sci., 25(5):641-666, 2014. URL: http://dx.doi.org/10.1142/S0129054114500269.
  16. Manfred Droste and Heiko Vogler. Weighted tree automata and weighted logics. Theor. Comput. Sci., 366(3):228-247, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.08.025.
  17. Samuel Eilenberg. Automata, Languages, and Machines, volume 59-A of Pure and Applied Mathematics. Academic Press, 1974. Google Scholar
  18. Calvin C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Am. Math. Soc., 98(1):21-52, 1961. Google Scholar
  19. E. Allen Emerson. Temporal and modal logic. In Handbook of Theoretical Computer Science, Volume B, pages 995-1072. MIT Press, 1990. Google Scholar
  20. Robert W. Floyd. Syntactic analysis and operator precedence. J. ACM, 10(3):316-333, 1963. Google Scholar
  21. D. Grune and C. J. Jacobs. Parsing techniques: a practical guide. Springer, New York, 2008. Google Scholar
  22. Donald E. Knuth. Semantics of context-free languages. Mathematical Systems Theory, 2(2):127-145, 1968. Google Scholar
  23. Werner Kuich and Arto Salomaa. Semirings, Automata, Languages, volume 6 of EATCS Monographs in Theoretical Computer Science. Springer, 1986. Google Scholar
  24. Clemens Lautemann, Thomas Schwentick, and Denis Thérien. Logics for context-free languages. In Leszek Pacholski and Jerzy Tiuryn, editors, Computer Science Logic, Selected Papers, volume 933 of LNCS, pages 205-216. Springer, 1994. Google Scholar
  25. Violetta Lonati, Dino Mandrioli, Federica Panella, and Matteo Pradella. Operator precedence languages: Their automata-theoretic and logic characterization. SIAM J. Comput., 44(4):1026-1088, 2015. URL: http://dx.doi.org/10.1137/140978818.
  26. Christian Mathissen. Weighted logics for nested words and algebraic formal power series. Logical Methods in Computer Science, 6(1), 2010. Selected papers of ICALP 2008. Google Scholar
  27. Robert McNaughton. Parenthesis grammars. J. ACM, 14(3):490-500, 1967. Google Scholar
  28. Robert McNaughton and Seymour Papert. Counter-free Automata. MIT Press, Cambridge, USA, 1971. Google Scholar
  29. Kurt Mehlhorn. Pebbling mountain ranges and its application of DCFL-recognition. In Automata, Languages and Programming, ICALP 1980, volume 85 of LNCS, pages 422-435, 1980. Google Scholar
  30. Maurice Nivat. Transductions des langages de Chomsky. Ann. de l'Inst. Fourier, 18:339-455, 1968. Google Scholar
  31. Arto Salomaa and Matti Soittola. Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science. Springer, 1978. Google Scholar
  32. Marcel Paul Schützenberger. On the definition of a family of automata. Inf. Control, 4(2-3):245-270, 1961. Google Scholar
  33. James Thatcher. Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Journ. of Comp. and Syst.Sc., 1:317-322, 1967. Google Scholar
  34. Boris A. Trakhtenbrot. Finite automata and logic of monadic predicates (in Russian). Doklady Akademii Nauk SSR, 140:326-329, 1961. Google Scholar
  35. Burchard von Braunmühl and Rutger Verbeek. Input-driven languages are recognized in log n space. In Proceedings of the Symposium on Fundamentals of Computation Theory, volume 158 of LNCS, pages 40-51. Springer, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact