Minimum number of generator assemblies

**elytkiat** · September 8th 2009, 06:23 AM

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$ ?

**NonCommAlg** · September 8th 2009, 03:42 PM

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?

**elytkiat** · September 9th 2009, 12:41 AM

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"?

Thread: Minimum number of generator assemblies

LinkBack

Thread Tools

Display

Minimum number of generator assemblies

Similar Math Help Forum Discussions

R Language Random Number Generator

Minimum Number

Minimum Number of Lawns

Random Number Generator

Search Tags