SOME DECISIONAL PROBLEMS ON RATIONAL RELATIONS

Authors
MADONIA M VARRICCHIO S
Citation
M. Madonia et S. Varricchio, SOME DECISIONAL PROBLEMS ON RATIONAL RELATIONS, Theoretical computer science, 180(1-2), 1997, pp. 1-15
Citations number
15
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
180
Issue
1-2
Year of publication
1997
Pages
1 - 15
Database
ISI
SICI code
0304-3975(1997)180:1-2<1:SDPORR>2.0.ZU;2-Y
Abstract
In this paper we prove that the problem of deciding whether a determin istic rational relation is star-free is recursively solvable, although the same problem for any rational relation is undecidable. We also pr ove that a rational relation is star-free if and only if it is aperiod ic and deterministic.