# Minimum number of generator assemblies

• Sep 8th 2009, 07: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 $\{1,...,n\}$ to $\{1,...,n\}$ with the operation of function composition, with a set of generators $\{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 $n$?
• Sep 8th 2009, 04: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 $\{1,...,n\}$ to $\{1,...,n\}$ with the operation of function composition, with a set of generators $\{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 $n$?

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

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

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