Weighted operator precedence languages
From MaRDI portal
Publication:2064530
DOI10.1016/J.IC.2020.104658zbMATH Open1483.68162arXiv1702.04597OpenAlexW3109871652MaRDI QIDQ2064530FDOQ2064530
Manfred Droste, Dino Mandrioli, Matteo Pradella, Stefan Dรผck
Publication date: 6 January 2022
Published in: Information and Computation (Search for Journal in Brave)
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 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"uchi-like theorem, we show that weighted OPA are expressively equivalent to a weighted MSO-logic for OPL.
Full work available at URL: https://arxiv.org/abs/1702.04597
quantitative logicquantitative automatavisibly pushdown languagesinput-driven languagesoperator precedence languages
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Handbook of weighted automata
- Adding nesting structure to words
- On the definition of a family of automata
- Parenthesis Grammars
- Weak SecondโOrder Arithmetic and Finite Automata
- Decision Problems of Finite Automata Design and Related Arithmetics
- Semantics of context-free languages
- Weighted versus Probabilistic Logics
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- First-order logics: some characterizations and closure properties
- Weighted automata and weighted MSO logics for average and long-time behaviors
- Weighted automata and weighted logics
- A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance Logic
- Weighted automata and multi-valued logics over arbitrary bounded lattices
- Weighted nested word automata and logics over strong bimonoids
- Weighted automata and logics for infinite nested words
- Weighted tree automata and weighted logics
- Transductions des langages de Chomsky
- Syntactic Analysis and Operator Precedence
- Operator precedence and the visibly pushdown property
- Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization
- Algebraic properties of operator precedence languages
- Some properties of precedence languages
- Colored Nested Words
- Weighted Operator Precedence Languages
- A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties
- Weighted Unranked Tree Automata over Tree Valuation Monoids and Their Characterization by Weighted Logics
- Weighted Logics for Nested Words and Algebraic Formal Power Series
- RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA
Recommendations
- Title not available (Why is that?) ๐ ๐
- Precedences in specifications and implementations of programming languages ๐ ๐
- Operator precedence and the visibly pushdown property ๐ ๐
- Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization ๐ ๐
- Some properties of precedence languages ๐ ๐
- Operational semantics of rewriting with priorities ๐ ๐
- Weighted Operator Precedence Languages ๐ ๐
- Operator Precedence and the Visibly Pushdown Property ๐ ๐
- Beyond operator-precedence grammars and languages ๐ ๐
- Operator Precedence ฯ-Languages ๐ ๐
This page was built for publication: Weighted operator precedence languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2064530)
