6533b85afe1ef96bd12ba041
RESEARCH PRODUCT
Some decisional problems on rational relations
Marina MadoniaStefano Varricchiosubject
TheoryofComputation_MISCELLANEOUSDiscrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESGeneral Computer ScienceTheoretical Computer ScienceUndecidable problemTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESIf and only ifAperiodic graphComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATIONAstrophysics::Solar and Stellar AstrophysicsRational relationComputer Science::Formal Languages and Automata TheoryAstrophysics::Galaxy AstrophysicsComputer Science(all)Mathematicsdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1997-06-01 | Theoretical Computer Science |