Weighted operator precedence languages
From MaRDI portal
Publication:2064530
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.
Recommendations
- Weighted operator precedence languages
- Higher-order operator precedence languages
- Operator precedence \(\omega \)-languages
- Beyond operator-precedence grammars and languages
- Some properties of precedence languages
- Precedences in specifications and implementations of programming languages
- Operator precedence and the visibly pushdown property
- Operator precedence and the visibly pushdown property
- Operator precedence languages: their automata-theoretic and logic characterization
- Operational semantics of rewriting with priorities
Cites work
- scientific article; zbMATH DE number 3876636 (Why is no real title available?)
- scientific article; zbMATH DE number 3932372 (Why is no real title available?)
- scientific article; zbMATH DE number 3696500 (Why is no real title available?)
- scientific article; zbMATH DE number 41838 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3588051 (Why is no real title available?)
- scientific article; zbMATH DE number 3639163 (Why is no real title available?)
- scientific article; zbMATH DE number 1142326 (Why is no real title available?)
- scientific article; zbMATH DE number 2079028 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- A Nivat theorem for weighted timed automata and weighted relative distance logic
- A unifying survey on weighted logics and weighted automata. Core weighted logic: minimal and versatile specification of quantitative properties
- Adding nesting structure to words
- Algebraic properties of operator precedence languages
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Colored Nested Words
- Decision Problems of Finite Automata Design and Related Arithmetics
- First-order logics: some characterizations and closure properties
- Handbook of weighted automata
- On the definition of a family of automata
- Operator Precedence Languages: Their Automata-Theoretic and Logic Characterization
- Operator precedence and the visibly pushdown property
- Parenthesis Grammars
- Recognizable and logically definable languages of infinite computations in concurrent automata
- Semantics of context-free languages
- Some properties of precedence languages
- Syntactic Analysis and Operator Precedence
- Transductions des langages de Chomsky
- Weak Second‐Order Arithmetic and Finite Automata
- Weighted automata and multi-valued logics over arbitrary bounded lattices
- Weighted automata and weighted MSO logics for average and long-time behaviors
- Weighted automata and weighted logics
- Weighted logics for nested words and algebraic formal power series
- Weighted nested word automata and logics over strong bimonoids
- Weighted operator precedence languages
- Weighted tree automata and weighted logics
- Weighted unranked tree automata over tree valuation monoids and their characterization by weighted logics
- Weighted versus Probabilistic Logics
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)
