As in the explicit and symbolic cases, the problem becomes non trivial for TDP/PDP only when \(|\Sigma _\mathcal {B}| < \min \lbrace |\Sigma _\mathcal {I}|, |\Sigma _\mathcal {O}|\rbrace \) .
While TDP/PDP in the symbolic setting can be solved by reduction to the explicit setting, this cannot be done here
as the domains are possibly infinite. Indeed, automatic-relation TDP/PDP seems to be a challenging problem.
We next conjecture that automatic-relation TDP/PDP is undecidable and
explain the motivation for this conjecture and why an automata-theoretic approach may not be helpful for TDP/PDP. We then show that even for the most basic case, in which the given relation is the equality relation, TDP/PDP can already be viewed as an algorithmic problem in automata that is equivalent to the Positivity Problem whose decidability is still open [1]}, [2]}.
Then, we show that for an intermediate alphabet that is of size of power of 2, TDP/PDP on automatic relations can be reduced to TDP/PDP on binary intermediate alphabet.
Finally we show by an automata-theoretic approach that a “strategic" variant of PDP, in which the required relations are in form of transducers, is decidable, and in fact is in EXPTIME.
