Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b]
Also you can assume that a,c≠𝜀 but you cannot assume so for b and d.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It's really simple. Just build two finite state transducers A and B , one for each substitution, then perform their composition A○B and B○A check if they are equivalent. Checking equivalence of transducers is undecidable, but in this case the transducers should be functional and equivalence in this special case is decidable.