2DST mappings on languages and related problems

AbstractLet l be a family of languages effectively closed under inverse homomorphism and intersection with regular sets and such that the languages have effectively constructible semilinear Parikh maps. We show that there is an algorithm to decide given a language L in L and a language R accepted by a one-way nondeterministic multicounter machine, where each counter makes exactly one reversal, whether L∩R is empty. This result has many applications. In particular, it can be used to show that there is an algorithm to decide given a language L in L and two-way deterministic sequential transducers (2DST's) S1 and S2 whether S1 and S2 are equivalent on L