0000000000470772
AUTHOR
Raivis Bets
On the Existence of 1-Bounded Bi-ideals with the WELLDOC Property
A combinatorial condition called well distributedoccurrences, or WELLDOC for short, has been introducedrecently. The proofs that WELLDOC property holds for thefamily of Sturmian words, and more generally, for Arnoux-Rauzy words are given in two papers by Balkova et al. The WELLDOC property for bounded bi-ideals is analysed inthis paper. The existence of a 1-bounded bi-ideal over thefinite alphabet that satisfies the WELLDOC property has beenproved by the authors.
Partial Finitely Generated Bi-Ideals
Partial words have been studied by Blanchet-Sadri et al., but bi-ideals or reccurrent words have been studied for centuries by many researchers. This paper gives a solution for some problems for partial reccurrent words. This paper gives an algorithm for a given finitely generated bi-ideal, how to construct a new basis of ultimately finitely generated bi-ideal, which generates the same given bi-ideal. The paper states that it is always possible to find a basis for a given finitely generated bi-ideal. The main results of this paper are presented in third section. At first, we show that if two irreduciable bi-ideals are different, they will differ in infinitely many places. This led to the st…
Bounded Bi-ideals and Linear Recurrence
Bounded bi-ideals are a subclass of uniformly recurrent words. We introduce the notion of completely bounded bi-ideals by imposing a restriction on their generating base sequences. We prove that a bounded bi-ideal is linearly recurrent if and only if it is completely bounded.
On a Non-periodic Shrinking Generator
We present a new non-periodic random number generator based on the shrinking generator. The A-sequence is still generated using a LFSR, but the S-sequence is replaced by a finitely generated bi-ideal - a non-periodic sequence. The resulting pseudo-random sequence performs well in statistical tests. We show a method for the construction of an infinite number of finitely generated bi-ideals from a given A-sequence, such that the resulting sequence of the shrinking generator is nonperiodic. Further we prove the existence of what we call universal finitely generated bi-ideals that produce non-periodic words when used as the S-sequence of a shrinking generator for all non-trivial periodic A-sequ…