<p>A <a href="https://en.wikipedia.org/wiki/Unary_language" rel="nofollow">tally language</a> is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P_1$ (the tally languages that can be decided in polynomial time).</p>

<p>Consider the non-unary alphabet $A = \{0, 1\}$.
Say I have a language $L$ on $A$ such that there is a unary language $L_1$ on the singleton alphabet $\{1\}$ with $L = \{w \in A^* \mid 1^{|w|} \in L_1\}$. In other words, $L$ is the language of words on $A$ whose length (written as a string of $1$'s) is in $L_1$.</p>

<p>The language $L$ is not a tally language, because it is not on a unary alphabet. Intuitively, however, it's not very far from being one: it can be decided only from the length of the input, or in other words it is a tally language "up to remapping the alphabet". <strong>Is there a standard name for such a language?</strong></p>

<p>Further, if I consider the class of all such languages on $A$, for tally languages that range in a given tally complexity class (say, $P_1$), is there a standard name for the resulting non-tally class?</p>

CC BY-SA 3.0
2015-11-04T21:18:26.113Z
So, simply the closure of the class under inverse length-preserving morphisms, right?
Michaël Cadilhac
CC BY-SA 3.0
2015-11-04T21:56:22.330Z
@MichaëlCadilhac: Yes, I guess that's one way to say it.
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-11-05T08:18:01.203Z
Every tally language is sparse, but not all non-tally languages (as you define them) are sparse.
If $C$ is a tally complexity class, the corresponding non-tally class is included in $C/poly$.
Boson
<cc.complexity-theory><reference-request><complexity-classes><unary-languages>
Complexity classes for problems that can be solved only from the length of the input
Antoine Amarilli 'a3nm'
# Complexity classes for problems that can be solved only from the length of the input

(Asked by: username_0 on 2015-11-04)

A [tally language](https://en.wikipedia.org/wiki/Unary_language) is a language on an alphabet with only one symbol. One can define complexity classes for tally languages, such as $P\_1$ (the tally languages that can be decided in polynomial time).

Consider the non-unary alphabet $A = \{0, 1\}$.
Say I have a language $L$ on $A$ such that there is a unary language $L\_1$ on the singleton alphabet $\{1\}$ with $L = \{w \in A^\* \mid 1^{|w|} \in L\_1\}$. In other words, $L$ is the language of words on $A$ whose length (written as a string of $1$'s) is in $L\_1$.

The language $L$ is not a tally language, because it is not on a unary alphabet. Intuitively, however, it's not very far from being one: it can be decided only from the length of the input, or in other words it is a tally language "up to remapping the alphabet". **Is there a standard name for such a language?**

Further, if I consider the class of all such languages on $A$, for tally languages that range in a given tally complexity class (say, $P\_1$), is there a standard name for the resulting non-tally class?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, unary-languages
> **Comments:**
> **username_1**: So, simply the closure of the class under inverse length-preserving morphisms, right?  
> **username_0**: @MichaëlCadilhac: Yes, I guess that's one way to say it.  
> **username_2**: Every tally language is sparse, but not all non-tally languages (as you define them) are sparse. If $C$ is a tally complexity class, the corresponding non-tally class is included in $C/poly$.  

---

## 0 answers

