<p>The closest related family of languages seem to be the "bounded semilinear languages" defined in <a href="https://www.worldscientific.com/doi/abs/10.1142/S0129054112400539" rel="nofollow noreferrer">this paper</a>.  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".  </p>

CC BY-SA 4.0
2019-02-20T05:41:57.373Z
2019-02-20T05:41:57.373Z
Zed
<p>I was wondering whether there is a standard name in the literature for the following family <span class="math-container">$\mathcal{F}$</span> of languages over any finite alphabet <span class="math-container">$\Sigma = \{a_1,\ldots,a_k\}$</span>:</p>

<p><span class="math-container">$\mathcal{F}$</span> consists of all languages of the shape <span class="math-container">$\{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})\}$</span>, where <span class="math-container">$c_1,c_3,\ldots,c_k$</span> are fixed nonnegative constants and <span class="math-container">$R$</span> is any fixed relation on <span class="math-container">$m$</span> variables <span class="math-container">$u_1,u_2,\ldots,u_m$</span> such that for some <span class="math-container">$S \subseteq \{1,2,\ldots,m\} \times \{1,2,\ldots,m\}$</span>, <span class="math-container">$R(u_1,u_2,\ldots,u_m)$</span> holds iff <span class="math-container">$\left((\forall i,j \in \{1,\ldots,m\})[u_i = u_j \Leftrightarrow (i,j) \in S]\right)$</span>.</p>

<p>So <span class="math-container">$\mathcal{F}$</span> contains languages like <span class="math-container">$\{a_1^n a_2^n a_3^n: n \geq 0\}$</span> (the "standard" context-sensitive but non-context-free language) and <span class="math-container">$\{a_1^2 a_1^n a_2^m a_1 a_1^m a_2^n a_1: n,m \geq 0\}$</span>.</p>

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

<p>Thank you!       </p>

CC BY-SA 4.0
2019-02-13T07:33:13.503Z
This is a very special case of the family mentioned in https://cstheory.stackexchange.com/q/17976/5038.  Perhaps that would be helpful for finding related literature.
D.W.
<reference-request><automata-theory>
Name for a special family of languages?
Zed
# Name for a special family of languages?

(Asked by: username_0 on 2019-02-13)

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!

**Tags:** reference-request, automata-theory

> **Comments:**
> **username_1**: This is a very special case of the family mentioned in https://cstheory.stackexchange.com/q/17976/5038.  Perhaps that would be helpful for finding related literature.  

---

## 1 answers

### Answer by username_0 on 2019-02-20. Score: 1

The closest related family of languages seem to be the "bounded semilinear languages" defined in [this paper](https://www.worldscientific.com/doi/abs/10.1142/S0129054112400539). 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".


---

