Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T07:21:36.787Z Has data issue: false hasContentIssue false

Decision problems among the main subfamiliesof rational relations

Published online by Cambridge University Press:  20 July 2006

Olivier Carton
Affiliation:
LIAFA, Université Paris 7 & CNRS, 2 pl. Jussieu, 75251 Paris Cedex 05, France; Christian.Choffrut@liafa.jussieu.fr
Christian Choffrut
Affiliation:
LIAFA, Université Paris 7 & CNRS, 2 pl. Jussieu, 75251 Paris Cedex 05, France; Christian.Choffrut@liafa.jussieu.fr
Serge Grigorieff
Affiliation:
LIAFA, Université Paris 7 & CNRS, 2 pl. Jussieu, 75251 Paris Cedex 05, France; Christian.Choffrut@liafa.jussieu.fr
Get access

Abstract

We consider the four families of recognizable, synchronous,deterministic rational and rational subsets of a direct productof free monoids.They form a strict hierarchy and we investigate the followingdecision 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 uniquegenerator and fill some gaps in the general case.In particular, adapting a proof of Stearns, we show that it is recursively decidablewhether or not a deterministic subset of an arbitrarynumber of free monoids is recognizable.Also we exhibit a single exponential algorithmfor determining if a synchronous relation is recognizable.

Information

Type
Research Article
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable