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?

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

0

Reset to default

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.