0000000000994595

AUTHOR

Marina Madonia

showing 3 related works from this author

A generalization of Sardinas and Patterson's algorithm to z-codes

1993

Abstract This paper concerns the framework of z-codes theory. The main contribution consists in an extension of the algorithm of Sardinas and Patterson for deciding whether a finite set of words X is a z-code. To improve the efficiency of this test we have found a tight upper bound on the length of the shortest words that might have a double z-factorization over X. Some remarks on the complexity of the algorithm are also given. Moreover, a slight modification of this algorithm allows us to compute the z-deciphering delay of X.

CombinatoricsSardinas–Patterson algorithmGeneral Computer ScienceGeneralizationCode (cryptography)Extension (predicate logic)Finite setUpper and lower boundsAlgorithmComputer Science(all)Theoretical Computer ScienceMathematicsAutomatonTheoretical Computer Science
researchProduct

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