Undecidable problems concerning densities of languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Undecidable problems concerning densities of languages

Résumé

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} )$.
Fichier principal
Vignette du fichier
dmAF0105.pdf (166.46 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01183335 , version 1 (12-08-2015)

Identifiants

Citer

Jakub Kozik. Undecidable problems concerning densities of languages. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. pp.69-76, ⟨10.46298/dmtcs.3471⟩. ⟨hal-01183335⟩
40 Consultations
589 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More