2
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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