6533b856fe1ef96bd12b268a
RESEARCH PRODUCT
A generalization of Sardinas and Patterson's algorithm to z-codes
Marina MadoniaSergio SalemiT. Sportellisubject
CombinatoricsSardinas–Patterson algorithmGeneral Computer ScienceGeneralizationCode (cryptography)Extension (predicate logic)Finite setUpper and lower boundsAlgorithmComputer Science(all)Theoretical Computer ScienceMathematicsAutomatondescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1993-02-01 | Theoretical Computer Science |