Synchronized rational relations of finite and infinite words (Q685453)

Rational relations on finite and infinite words are considered. The emphasis is on the synchronized (letter-to-letter) rational relations and the rational relations that are computed by automata with bounded delay. The authors make use of the resynchronization lemma of Eilenberg and Schützenberger. This result is generalized for infinite words. For the finite words it is shown that the synchronized rational relations are deterministic rational relations. Moreover, it is shown that it is undecidable whether a rational relation is synchronized or not. For infinite words it is proved that the family of deterministic synchronized rational relations is the intersection of the families of synchronized rational relations and deterministic rational relations.