The identity problem of finitely generated bi-ideals (Q2428497)

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.