Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (649kB) | Preview |
The Parikh property for weighted Context-Free Grammars
Citation
Ganty, Pierre and Gutiérrez Viedma, Elena (2018). The Parikh property for weighted Context-Free Grammars. In: "38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)", 11-13 Dic 2018, Ahmedabad, India. ISBN 978-3-95977-093-4. pp. 495-514. https://doi.org/10.4230/LIPIcs.FSTTCS.2018.32.
Description
| Title: | The Parikh property for weighted Context-Free Grammars |
|---|---|
| Author/s: |
|
| Item Type: | Presentation at Congress or Conference (Article) |
| Event Title: | 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018) |
| Event Dates: | 11-13 Dic 2018 |
| Event Location: | Ahmedabad, India |
| Title of Book: | FSTTCS 2018 : 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
| Date: | 2018 |
| ISBN: | 978-3-95977-093-4 |
| Volume: | 122 |
| Subjects: | |
| Freetext Keywords: | Weighted Context-Free Grammars; Algebraic Language Theory; Parikh Image |
| Faculty: | E.T.S. de Ingenieros Informáticos (UPM) |
| Department: | Otro |
| Creative Commons Licenses: | Recognition - No derivative works - Non commercial |
Abstract
The Parikh Theorem states that every context-free grammar (CFG) is equivalent to some regular CFG when the ordering of symbols in the words is ignored. The same is not true for the so-called weighted CFGs, which additionally assign a weight to each grammar rule. If the result holds for a given weighted CFG G, we say that G satisfies the Parikh property. We prove constructively that the Parikh property holds for every weighted nonexpansive CFG. We also give a decision procedure for the property when the weights are over the rationals.
Funding Projects
| Type | Code | Acronym | Leader | Title |
|---|---|---|---|---|
| Government of Spain | BES-2016-077136 | Unspecified | Fundación IMDEA Software | Unspecified |
| Government of Spain | TIN2015-71819-P | RISCO | Fundación IMDEA Software | Tecnologías rigurosas para el análisis y verificación de software concurrente y distribuido sofisticado |
| Government of Spain | RYC-2016-20281 | Unspecified | Fundación IMDEA Software | Unspecified |
More information
| Item ID: | 62635 |
|---|---|
| DC Identifier: | http://oa.upm.es/62635/ |
| OAI Identifier: | oai:oa.upm.es:62635 |
| DOI: | 10.4230/LIPIcs.FSTTCS.2018.32 |
| Official URL: | https://drops.dagstuhl.de/opus/volltexte/2018/9931/ |
| Deposited by: | Memoria Investigacion |
| Deposited on: | 01 Jun 2020 17:49 |
| Last Modified: | 01 Jun 2020 17:49 |
