A generalization of Sardinas and Patterson’s algorithm to \(Z\)-codes. (English) Zbl 0778.68052

Summary: The paper concerns the framework of \(Z\)-codes theory. The main contribution consists in a new algorithm for deciding whether a finite set of words \(X\) is a \(Z\)-code. This algorithm is based on a nontrivial extension of the well-known test on codes due to Sardinas and Patterson.
Moreover slight modification of this algorithm allows to compute the \(Z\)- deciphering delay of a \(Z\)-code. Its nature is essentially combinatorial. To show the correctness of the algorithm, a theorem, which gives a characterization of the \(Z\)-codes, is given.
The paper contains also a detailed complexity analysis of the algorithm. Particular attention is devoted to find an efficient halt condition of the test and this effort carries out a new upper bound on the length of the shortest words that might have double \(Z\)-factorization. This bound is tight.


68Q45 Formal languages and automata
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
68R15 Combinatorics on words
Full Text: DOI


[1] Anselmo, M., Automates et codes zigzag, RAIRO Inform. Théor. Appl., 25, 1 (1991) · Zbl 0735.68050
[3] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[4] Madonia, M.; Salemi, S.; Sportelli, T., On \(z\)-submonoids and \(z\)-codes, RAIRO Inform. Théor. Appl., 25, 4 (1991) · Zbl 0764.68089
[5] Pécuchet, J. P., Automates boustrophédons, langages reconnaisables de mots infinis et variétés de semigroupes, Thèse d’Etat (1986), LITP
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.