1 Search Results for "Pradella, Matteo"

Document
DOI: 10.4230/LIPIcs.MFCS.2017.31
Weighted Operator Precedence Languages

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

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{droste_et_al:LIPIcs.MFCS.2017.31,
  author =	{Droste, Manfred and D\"{u}ck, Stefan and Mandrioli, Dino and Pradella, Matteo},
  title =	{{Weighted Operator Precedence Languages}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.31},
  URN =		{urn:nbn:de:0030-drops-81150},
  doi =		{10.4230/LIPIcs.MFCS.2017.31},
  annote =	{Keywords: Quantitative automata, operator precedence languages, input-driven languages, visibly pushdown languages, quantitative logic}
}
  • Refine by Author
  • 1 Droste, Manfred
  • 1 Dück, Stefan
  • 1 Mandrioli, Dino
  • 1 Pradella, Matteo

  • Refine by Classification

  • Refine by Keyword
  • 1 Quantitative automata
  • 1 input-driven languages
  • 1 operator precedence languages
  • 1 quantitative logic
  • 1 visibly pushdown languages

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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 Imprint Privacy Contact