The Parikh property for weighted Context-Free Grammars

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:
  • Ganty, Pierre
  • Gutiérrez Viedma, Elena
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

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (649kB) | Preview

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

TypeCodeAcronymLeaderTitle
Government of SpainBES-2016-077136UnspecifiedFundación IMDEA SoftwareUnspecified
Government of SpainTIN2015-71819-PRISCOFundación IMDEA SoftwareTecnologías rigurosas para el análisis y verificación de software concurrente y distribuido sofisticado
Government of SpainRYC-2016-20281UnspecifiedFundación IMDEA SoftwareUnspecified

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
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM