0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ So, simply the closure of the class under inverse length-preserving morphisms, right? $\endgroup$ – Michaël Cadilhac Nov 4 '15 at 21:18
  • $\begingroup$ @MichaëlCadilhac: Yes, I guess that's one way to say it. $\endgroup$ – a3nm Nov 4 '15 at 21:56
  • $\begingroup$ 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$. $\endgroup$ – Boson Nov 5 '15 at 8:18

Your Answer

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

Browse other questions tagged or ask your own question.