0000000000164015
AUTHOR
Janis Buls
Machine Morphisms And Simulation
This paper examines the concept of simulation from a modelling viewpoint. How can one Mealy machine simulate the other one? We create formalism for simulation of Mealy machines. The injective s–morphism of the machine semigroups induces the simulation of machines [1]. We present the example of s–morphism such that it is not a homomorphism of semigroups. The story for the surjective s–morphisms is quite different. These are homomorphisms of semigroups but there exists the surjective s–morphism such that it does not induce the simulation.
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…
Representation of Autonomous Automata
An autonomous automaton is a finite automaton with output in which the input alphabet has cardinality one when special reduced. We define the transition from automata to semigroups via a representation successful if given two incomparable automata (neither simulate the other), the semigroups representing the automata are distinct. We show that representation by the transition semigroup is not successful. We then consider a representation of automata by semigroups of partial transformations. We show that in general transition from automata to semigroups by this representation is not successful either. In fact, the only successful transition presented is the transiton to this semigroup of par…