0000000001053453

AUTHOR

Stefano Varricchio

showing 2 related works from this author

Iterative pairs and multitape automata

1996

In this paper we prove that if every iterative k-tuple of a language L recognized by a k-tape automaton is very degenerate, then L is recognizable. Moreover, we prove that if L is an aperiodic langnage recognized by a deterministic k-tape automaton, then L is recognizable.

ComputingMilieux_GENERALDiscrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESFinite-state machineAperiodic graphFree monoidDegenerate energy levelsMathematicsAutomaton
researchProduct

Some decisional problems on rational relations

1997

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.

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)MathematicsTheoretical Computer Science
researchProduct