Geodesic
Undecidable problems concerning densities of languages
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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} )$. 
@article{DMTCS_2005_special_251_a3,
     author = {Kozik, Jakub},
     title = {Undecidable problems concerning densities of languages},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3471},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3471/}
}
TY  - JOUR
AU  - Kozik, Jakub
TI  - Undecidable problems concerning densities of languages
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3471/
DO  - 10.46298/dmtcs.3471
LA  - en
ID  - DMTCS_2005_special_251_a3
ER  - 
%0 Journal Article
%A Kozik, Jakub
%T Undecidable problems concerning densities of languages
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3471/
%R 10.46298/dmtcs.3471
%G en
%F DMTCS_2005_special_251_a3
Kozik, Jakub. Undecidable problems concerning densities of languages. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) (2005). doi : 10.46298/dmtcs.3471. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3471/

Cité par Sources :