Deciding Whether or Not a Synchronous Relation is Regular Prefix

Abstract

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then Läuchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentally we also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.