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

Madonia, M.; Salemi, S.; Sportelli, T.

Theor. Comput. Sci. 108, No. 2, 251-270 (1993).

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.

MSC:

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

Keywords:

algorithms on \(Z\)-codes; \(Z\)-deciphering delay; upper bound; double \(Z\)- factorization

References:

[1]	Anselmo, M., Automates et codes zigzag, RAIRO Inform. Théor. Appl., 25, 1 (1991) · Zbl 0735.68050
[2]	M. Anselmo, Sur les codes zigzag et leur décidabilité, Report LITP 89.36.; M. Anselmo, Sur les codes zigzag et leur décidabilité, Report LITP 89.36. · Zbl 0701.68057
[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