Can the catenation of two weakly sparse languages be dense?

DOI10.1016/0166-218X(88)90083-2zbMath0644.68102OpenAlexW2082432017MaRDI QIDQ1102760

Sheng Yu

Publication date: 1988

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(88)90083-2

zbMATH Keywords

dense languageweakly sparse languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

On sparse languages \(L\) such that \(LL= \Sigma^*\) ⋮ Characterizing regular languages with polynomial densities

Cites Work

• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• On Isomorphisms and Density of $NP$ and Other Complete Sets

This page was built for publication: Can the catenation of two weakly sparse languages be dense?