Rational relations having a rational trace on each finite intersection of rational relations
We consider the family of rational relations on words, i.e., relations recognized by multitape automata, which have rational trace on any finite intersection of rational relations. We prove that this family consists of finite unions of relations which are of two types: stars of tuples possibly with an extra prefix and suffix and relations with all but one singleton set components. (C) 2012 Elsevier B.V. All rights reserved.
rational relation automata