Therefore the problem of TDP in this setting is reduced to the following problem: given a regular language \(L\)  over a finite alphabet \(\Sigma \) ,
where for every \(n\) , \(L_n\)  is the set of words in \(L\)  of size \(n\) , does \(|L_n|\le 2^n\)  for every \(n\) ? We call this problem the
The Exponential-Bound Problem (EBP). The following theorem, however, shows that EBP is equivalent to the problem of Positivity, described below, whose decidability has been famously open for decades  [1]}, [2]}. By equivalent, we mean that there is a many-to-one reduction from EBP to Positivity and vica versa.
Although this is not a direct reduction to automatic TDP, this relation indicates the hardness of
solving automatic TDP on even a simple relation.
