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...

Fuld beskrivelse

Bibliografiske detaljer

Hovedforfatter:	Jakub Kozik
Format:	Artigo
Sprog:	Inglês
Udgivet:	Discrete Mathematics & Theoretical Computer Science 2005-01-01
Serier:	Discrete Mathematics & Theoretical Computer Science
Fag:	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]
Online adgang:	https://dmtcs.episciences.org/3471/pdf
Tags:	Tilføj Tag Ingen Tags, Vær først til at tagge denne postø!