On sparse languages \(L\) such that \(LL= \Sigma^*\)
type: Item
instance of: scholarly article
title: On sparse languages \(L\) such that \(LL= \Sigma^*\)
zbMATH Open document ID: 0813.68124
DOI: 10.1016/0166-218X(94)90146-5
author: Per Enflo
author: Andrew Granville
author: Jeffrey Shallit
author: Sheng Yu
published in: Discrete Applied Mathematics
publication date: 1994-09-27T00:00:00Z
review text: A language \(L \in \Sigma^*\) is called a sparse language if \(L\) contains a small part of all the possible strings of length \(n\) (more precisely, \(\lim_{n \to \infty} | L cap \Sigma^{\leq n}| /| \Sigma^{\leq n}| = 0\), where \(\Sigma^{\leq n}\) is the set of all the strings over \(\Sigma\) having the length at most \(n\)). The paper provides different constructions (using ideas from probability theory, fractal geometry and analytic number theory) for getting languages \(L\) over \(\Sigma\) such that \(L\) is a sparse language and \(LL = \Sigma^*\) -- an open problem due to C. Ponder. Finally a generalization of this problem, \(L\) is sparse and \(L^ j = \Sigma^*\) is also developed.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 626250
zbMATH Keywords: sparse language
reviewed by: Marian Gheorghe
MaRDI profile type: Publication
cites work: Über Basen der natürlichen Zahlenreihe
cites work: Q5541610
cites work: Long repetitive patterns in random sequences
cites work: Q4052222
cites work: Q3963072
cites work: Q5772619
cites work: Q4769112
cites work: Q5592246
cites work: Q3724287
cites work: Can the catenation of two weakly sparse languages be dense?
full work available at URL: 0166-218x(94)90146-5
OpenAlex ID: W1480028229
description: scientific article; zbMATH DE number 626250