×

The identity problem of finitely generated bi-ideals. (English) Zbl 1258.68109

The study of bi-ideal sequences stems from the concept of a bi-ideal in a free semigroup. Beside a purely algebraic motivation of the research, it is worth mentioning that finitely generated bi-ideals may serve as stream cipher keystream generators in cryptography.
An infinite word \(x\) over an alphabet \(A\) is a bi-ideal if there exists an infinite sequence of finite words \(u_{0},u_{1},\ldots\in A^{\ast}\) such that \(x=v_{0}u_{1}v_{0}u_{2} v_{1}\cdots u_{n}v_{n-1}\cdots\), where \(v_{0}=u_{0}\) and \(v_{i}=v_{i-1} u_{n}v_{i-1}\) (thus \(x=\lim_{i\rightarrow\infty}v_{i}\)). A bi-ideal \(x\) is said to be finitely generated by the generating system (sequence) \(\left\langle u_{0},\ldots,u_{m-1}\right\rangle \) if, for \(i\geq0\), \(u_{i+m}=u_{i}\). Two generating systems are equivalent if they generate the same bi-ideal. The authors present a construction showing that every finitely generated bi-ideal is generated by countably many generating systems of the same length. Further, they provide an algorithm for deciding whether two given generating systems of length 2 are equivalent. The general problem of deciding the equivalence for generating systems of an arbitrary length remains open.

MSC:

68R15 Combinatorics on words
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allouche J.-P., Shallit J.: Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003) · Zbl 1086.11015
[2] Buls, J., Lorencs, A.: From bi-ideals to periodicity, XIth ”Mons days of Theoretical Computer Science”. In: Internal Proceedings IFSIC/IRISA, Rennes, France, pp. 97–110, August 30–September 2 2006
[3] Coudrain M., Schützenberger M.-P.: Une condition de finitude des monoïdes finiment engedrés. C. R. Acad. Sci. Paris, Sér. A, 262, 1149–1151 (1966) · Zbl 0141.01801
[4] de Luka A., Varrichio S.: Finiteness and Regularity in Semigroups and Formal Languages. Springer, Berlin (1999)
[5] Fine N.J., Wilf H.S.: Uniqueness theorem for periodic functions. Proc. Amer. Math. Soc. 16, 109–114 (1965) · Zbl 0131.30203 · doi:10.1090/S0002-9939-1965-0174934-9
[6] Good R.A., Hughes D.R.: Associated groups for a semigroup. Bull. Amer. Math. Soc. 58, 624–625 (1952)
[7] Lothaire, M.: Combinatorics on Words, 2nd edn. Cambridge University Press, Cambridge (1997); 1st edn 1983 · Zbl 0514.20045
[8] Lothaire M.: Applied Combinatorics on Words. Cambridge University Press, Cambridge (2005) · Zbl 1133.68067
[9] Stinson D.R.: Cryptography: Theory and Practice. CRC Press, Inc., Boca Raton (1995) · Zbl 0855.94001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.