Undecidable problems concerning densities of languages
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 relati...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3471/pdf |
| _version_ | 1797270600895430656 |
|---|---|
| author | Jakub Kozik |
| author_facet | Jakub Kozik |
| author_sort | Jakub Kozik |
| collection | DOAJ |
| description | 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} )$. |
| first_indexed | 2024-04-25T02:06:51Z |
| format | Article |
| id | doaj.art-0d91233d4c304431b3f1d66bc511e02a |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:06:51Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0d91233d4c304431b3f1d66bc511e02a2024-03-07T14:32:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AF,...Proceedings10.46298/dmtcs.34713471Undecidable problems concerning densities of languagesJakub Kozik0Faculty of Mathematics and Computer Science of the Jagiellonian UniversityIn 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} )$.https://dmtcs.episciences.org/3471/pdfasymptotic densitycontext-free languagesdecidability[info.info-lo] computer science [cs]/logic in computer science [cs.lo][info.info-sc] computer science [cs]/symbolic computation [cs.sc] |
| spellingShingle | Jakub Kozik Undecidable problems concerning densities of languages Discrete Mathematics & Theoretical Computer Science 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] |
| title | Undecidable problems concerning densities of languages |
| title_full | Undecidable problems concerning densities of languages |
| title_fullStr | Undecidable problems concerning densities of languages |
| title_full_unstemmed | Undecidable problems concerning densities of languages |
| title_short | Undecidable problems concerning densities of languages |
| title_sort | undecidable problems concerning densities of languages |
| topic | 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] |
| url | https://dmtcs.episciences.org/3471/pdf |
| work_keys_str_mv | AT jakubkozik undecidableproblemsconcerningdensitiesoflanguages |