Jakub Kozik - Undecidable problems concerning densities of languages

dmtcs:3471 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) - https://doi.org/10.46298/dmtcs.3471
Undecidable problems concerning densities of languagesArticle

Authors: Jakub Kozik 1

  • 1 Faculty of Mathematics and Computer Science of the Jagiellonian University

In this paper we prove that the question whether a language presented by a context free grammar has density, is undecidable. Moreover we show that there is no algorithm which, given two unambiguous context free grammars on input, decides whether the language defined by the first grammar has a relative density in the language defined by the second one. Our techniques can be extended to show that this problem is undecidable even for languages given by grammars from $LL(k)$ (for sufficiently large fixed $k ∈ \mathbb{N} )$.


Volume: DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: asymptotic density,context-free languages,decidability,[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO],[INFO.INFO-SC] Computer Science [cs]/Symbolic Computation [cs.SC]

Consultation statistics

This page has been seen 192 times.
This article's PDF has been downloaded 185 times.