# Minimum number of generator assemblies

• Sep 8th 2009, 06:23 AM
elytkiat
Minimum number of generator assemblies
Hi everyone. I'm new, and I'm not a native speaker of english, so I hope I won't get any of the advanced algebra names wrong. This is my question:

There is a finite semigroup of functions from the set $\displaystyle \{1,...,n\}$ to $\displaystyle \{1,...,n\}$ with the operation of function composition, with a set of generators $\displaystyle \{f,g\}$. We know that there exists a sequence of assemblies of these generators so that it produces a constant function. What is an upper bound on the length of the minimum number of assemblies for a specified $\displaystyle n$?
• Sep 8th 2009, 03:42 PM
NonCommAlg
Quote:

Originally Posted by elytkiat
Hi everyone. I'm new, and I'm not a native speaker of english, so I hope I won't get any of the advanced algebra names wrong. This is my question:

There is a finite semigroup of functions from the set $\displaystyle \{1,...,n\}$ to $\displaystyle \{1,...,n\}$ with the operation of function composition, with a set of generators $\displaystyle \{f,g\}$. We know that there exists a sequence of assemblies of these generators so that it produces a constant function. What is an upper bound on the length of the minimum number of assemblies for a specified $\displaystyle n$?

i'm not sure i understand the question: so you have two functions $\displaystyle f,g : \{1, \cdots , n \} \longrightarrow \{1, \cdots , n \}.$ we know that there exists an $\displaystyle m \geq 1$ such that $\displaystyle f_1f_2 \cdots f_m = \text{id},$ where $\displaystyle f_j \in \{f,g \}.$

now you're looking for an upper bound on what exactly?
• Sep 9th 2009, 12:41 AM
elytkiat
Yes, you got it right, and now the question is: what is the upper bound on the minimum number of $\displaystyle m$ (for a given $\displaystyle n$)?

In other words: what is the minimum $\displaystyle m$ in "the worst case scenario"?