The Parikh Property for Weighted Context-Free Grammars

DOI10.4230/LIPICS.FSTTCS.2018.32MaRDI QIDQ5090971zbMATH OpenOpenAlexFDO

Authors Pierre Ganty, Elena Gutiérrez

Publication date 21 July 2022

Full work available at URL https://arxiv.org/abs/1810.01351

zbMATH Keywords

Parikh imagealgebraic language theoryweighted context-free grammars

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Recommendations

• Extending Parikh's theorem to weighted and probabilistic context-free grammars
• Weighted context-free grammars over valuation monoid and their languages
• Parikh's theorem: a simple and direct automaton construction
• Weighted context-free grammars over bimonoids
• Weighted and probabilistic context-free grammars are equally expressive

Cites work

• scientific article; zbMATH DE number 4014944 (Why is no real title available?)
• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 3694623 (Why is no real title available?)
• scientific article; zbMATH DE number 1059894 (Why is no real title available?)
• A few remarks on the index of context-free grammars and languages
• A uniform framework for problems on context-free grammars
• Analyzing Real-Time Event-Driven Programs
• Extending Parikh's theorem to weighted and probabilistic context-free grammars
• Parikh's theorem: a simple and direct automaton construction
• The characterization of nonexpansive grammars by rational power series
• The complexity of equivalence problems for commutative grammars

Cited in

(2)

• Weighted Deductive Parsing and Knuth's Algorithm
• On polynomial recursive sequences

This page was built for publication: The Parikh Property for Weighted Context-Free Grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090971)