What does it mean for a language to be sparse?

Question

A language $A \subseteq \sum^{*}$ is sparse, and we write $A \in SPARSE$, if there is a polynomial q such that, for all $n \in N$,

$$\left|A \cap \sum^{n}\right|\leq q(n)$$

The definition of a polynomial is -

A polynomial is a function $q: N \to N$ for which there exists constants $c_0 ,..., c_k \in N$, such that for $n \in N$

$$q(n) = \sum_{i = 0}^{k}c_{i}n^{i}$$

Could someone explain to me why is A sparse? I understand that $A \cap \sum^{n}$ will only contain sets of length n and the cardinality of this set has to be less than $q(n)$. I am not sure what this inequality achieves.

Answer 1

Pick some alphabet $\Sigma$, and in particular focus on the “interesting” case where $|\Sigma| \ge 2$. Then $|\Sigma^n|$, the number of possible strings of length $n$, is equal to $|\Sigma|^n$. In other words, there are exponentially many possible strings of length $n$.

So now suppose you have a language $A$ meeting the requirements for a sparse language. That means there’s at most polynomially many strings of each length in $A$, even though there are exponentially many possible strings of each length. Since exponential functions grow significantly faster than polynomials, the language is “sparse” in the sense that very, very few of the possible strings end up being in $A$. If you were to list all strings in $\Sigma^*$ in order of length and scan through them looking for elements of $A$, they’d dramatically thin out as you got further and further down the list.

As for why we use polynomials here rather than other bounds, that’s largely because it aligns nicely with the sorts of questions we want to ask about languages in the context of problems like P versus NP. Many properties of sparse languages are easier to determine than of arbitrary languages precisely because there are only polynomially many strings of each length.

Answer 2

Not really an answer, but too long for a comment. You might be interested in this characterization of sparse regular languages.

Let $L$ be a regular language. The following conditions are equivalent:

1. $L$ is sparse,
2. $L$ is a finite union of languages of the form $u_0v_1^*u_1 \dotsm v_k^*u_k$, where $u_0, v_1, \ldots, v_k, u_k$ are words.
3. The minimal deterministic trimmed automaton of $L$ does not contain any forbidden pattern of the given form where $x$ and $y$ are nonempty words with different first letters.

$\hskip 100pt$