Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Decision problems among the main subfamilies of rational relations

Olivier CartonChristian ChoffrutSerge Grigorieff — 2006

RAIRO - Theoretical Informatics and Applications

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...

Page 1

Download Results (CSV)