Separating Automatic Relations

We study the separability problem for automatic relations (i. e. , relations on finite words definable by synchronous automata) in terms of recognizable relations (i. e. , finite unions of products of regular languages). This problem takes as input two automatic relations R and R', and asks if there exists a recognizable relation S that contains R and does not intersect R'. We show this problem to be undecidable when the number of products allowed in the recognizable relation is fixed. In particular, checking if there exists a recognizable relation S with at most k products of regular languages that separates R from R' is undecidable, for each fixed k ⩾ 2. Our proofs reveal tight connections, of independent interest, between the separability problem and the finite coloring problem for automatic graphs, where colors are regular languages.

Authors

• Pablo Barceló
• Diego Figueira
• Rémi Morvan

Keywords

• Automatic relations
• recognizable relations
• separability
• finite colorability