A tally 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?
Complexity classes for problems that can be solved only from the length of the input
cc.complexity theory;reference request;complexity classes;unary languages