Some decisional problems on rational relations

M.Madonia, S. Varricchio

IBP-Litp 1994/29: Rapport de Recherche Litp / Litp research reports
16 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Some decisional problems on rational relations

Résumé : Dans ce papier nous montrons que l'on peut décider si une relationnelle déterministe est sans étoile. Le même problème est indécidable pour une relation rationnelle quelconque. Nous montrons aussi qu'une relation rationnelle est sans étoile si et seulement si elle est apériodique et déterministe.

Abstract : In this paper we prove that the problem of deciding whether a deterministic rational relation is star-free is recursively solvable, although the same problem for any rational relation is undecidable. We also prove that a rational relation is star free if and only if it is aperiodic and deterministic.

Publications internes Litp 1994 / Litp research reports 1994