I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$:

$\mathcal{F}$ consists of all languages of the shape $\{a_{i_1}^{c_1}a_{i_2}^{n_2}a_{i_3}^{c_3}\ldots a_{i_{k-1}}^{n_{k-1}}a_{i_k}^{c_k}: n_2,n_4,\ldots,n_{k-1} \geq 0 \wedge R(n_2,n_4,\ldots,n_{k-1})\}$, where $c_1,c_3,\ldots,c_k$ are fixed nonnegative constants and $R$ is any fixed relation on $m$ variables $u_1,u_2,\ldots,u_m$ such that for some $S \subseteq \{1,2,\ldots,m\} \times \{1,2,\ldots,m\}$, $R(u_1,u_2,\ldots,u_m)$ holds iff $\left((\forall i,j \in \{1,\ldots,m\})[u_i = u_j \Leftrightarrow (i,j) \in S]\right)$.

So $\mathcal{F}$ contains languages like $\{a_1^n a_2^n a_3^n: n \geq 0\}$ (the "standard" context-sensitive but non-context-free language) and $\{a_1^2 a_1^n a_2^m a_1 a_1^m a_2^n a_1: n,m \geq 0\}$.

This family of languages cropped up in my work recently and I was wondering whether anything interesting could be said about it..

Thank you!

  • 1
    $\begingroup$ This is a very special case of the family mentioned in cstheory.stackexchange.com/q/17976/5038. Perhaps that would be helpful for finding related literature. $\endgroup$
    – D.W.
    Feb 13, 2019 at 7:33

1 Answer 1


The closest related family of languages seem to be the "bounded semilinear languages" defined in this paper. But since the commutative image of each language in the family defined in the original post is a linear set, it might be appropriate to call such languages "bounded linear".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.