Decision problems among the main subfamilies of rational relations
LIAFA, Université Paris 7 & CNRS,
2 pl. Jussieu, 75251 Paris Cedex 05, France; Christian.Choffrut@liafa.jussieu.fr
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether or not a deterministic subset of an arbitrary number of free monoids is recognizable. Also we exhibit a single exponential algorithm for determining if a synchronous relation is recognizable.
Mathematics Subject Classification: 3D05 / 68Q45
Key words: Multitape automata / Presburger arithmetics / decision problems.
© EDP Sciences, 2006