Undecidable problems concerning densities of languages

MaRDI QIDQ3576000zbMATH OpenFDO

Authors Jakub Kozik

Publication date 28 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAF0105/0.html

zbMATH Keywords

asymptotic densitycontext-free languagesdecidability

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35) Formal languages and automata (68Q45)

Recommendations

• Conditional densities of regular languages
• An undecidable property of context-free linear orders
• Density of grammar forms part II
• On the density of context-free and counter languages
• On the density of regular and context-free languages

Cited in

(16)

• A context-free language decision problem
• An undecidable property of context-free linear orders
• On the density of certain languages with \(p^2\) letters
• Conditional densities of regular languages
• (Un)decidability of the emptiness problem for multi-dimensional context-free grammars
• On the density of regular and context-free languages
• On the density of context-free and counter languages
• Density of grammar forms part II
• scientific article; zbMATH DE number 4080943 (Why is no real title available?)
• scientific article; zbMATH DE number 58306 (Why is no real title available?)
• On the density of context-free and counter languages
• scientific article; zbMATH DE number 938665 (Why is no real title available?)
• The two-cardinal problem for languages of arbitrary cardinality
• scientific article; zbMATH DE number 5199150 (Why is no real title available?)
• On the density of languages accepted by Turing machines and other machine models
• Relative densities of formal languages

This page was built for publication: Undecidable problems concerning densities of languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3576000)