0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.