Full text
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (649kB) | Preview |
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.
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 |
|
PDF
- Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (649kB) | Preview |
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.
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 |
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 |