On Equivalence Problem for Rational Relations

It is well-known that the containment and equivalence problems between rational relations is undecidable. In this talk, we study the decidability status of these problems between relations within certain subclasses of rational relations. In the 1960’s, Nivat showed that binary rational relations over a finite alphabet A correspond to 2-tape finite state automata that recognize regular languages L over the product alphabet {1,2}xA, where (i,a) is interpreted as reading letter a from tape i. Accordingly, a word w in L denotes the pair (u1, u2) in (A^*)^2 in which ui is the projection of w onto i-labelled letters. Enforcing restrictions on the reading regime from the tapes, which we call synchronization, yields various sub-classes of relations. Such synchronization restrictions are imposed through regular properties on the projection of the language L onto {1,2}. In this way, for each regular language C over the alphabet {1,2}^*, one obtains a class REL(C) of relations. Synchronous, Recognizable, and Length-preserving rational relations are all examples of classes that can be defined in this way. We characterize through a decidable property the classes of synchronized relations inside which the containment and equivalence problems are decidable. Interestingly, these classes are proved to be exactly those which are closed under intersection.

Authors

• Ismaël Jecker.

Keywords

No keywords are indexed for this paper.