A notable positive result about automatic relations is the decidability of their first-order theories [1]}, [2]}.
TDP/PDP are essentially second-order problems–we ask for the existence of \(R_1\)  and \(R_2\) 
under the TDP/PDP conditions.
Since there are second-order problems
over automatic relations that are known to be undecidable; for example, checking the existence of an Hamiltonian path in an automatic graph [3]}, our conjecture is that this problem is undecidable as well.
We provide here intuition to justify this conjecture.
