Results 1 to 3 of 3

Math Help - Minimum number of generator assemblies

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    2

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by elytkiat View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    2
    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"?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. R Language Random Number Generator
    Posted in the Advanced Statistics Forum
    Replies: 16
    Last Post: February 6th 2011, 04:32 AM
  2. Minimum Number
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 7th 2010, 07:07 AM
  3. Minimum Number of Lawns
    Posted in the Algebra Forum
    Replies: 2
    Last Post: December 11th 2008, 05:34 PM
  4. Random Number Generator
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: October 22nd 2008, 12:22 AM

Search Tags


/mathhelpforum @mathhelpforum