Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A finite state machine, FSM, is a box with C input/output channels, and S states, and a fixed map $f : S\times C \to S\times C\cup {0}$. If a state $(c_i,s_j)$ is mapped to the 0 element it means it enters a loop and cant exit.

Clearly if we join the channels of several FSM's pairwise, we obtain a new FSM, ie we get a system with some number of unjoined channels, C, and internal states given by the product of the number of internal states of each component FSM, S.

A composite FSM is allowed to have internal loops, ie we may never exit through an unjoined channel.

Is there a finite set of FSM's, by which every other FSM can be build?

Is there an algorithm to check if a target FSM can be build by any finite amounts of a given finite sets of FSM's?

share|cite|improve this question
Cross-posted at… –  Joel Reyes Noche Jan 14 '12 at 2:41
Your question is not well posed. What are the domain and range of f? Which map is determining the next state? Why not use usual automata theory language. I.e. are doors inputs, f an output function and there is a transition function you haven't named? Maybe you should look at te Krohn-Rhodes decomposition theorem. –  Benjamin Steinberg Jan 14 '12 at 12:39
Domain of is every pair of (input channel, internal state), range is some subset of this, we transition to the state f(c,s). –  knotted Jan 14 '12 at 12:53
But by your description f has images pairs, so not a state. Or are you sending it to the pair (outpu,next state). –  Benjamin Steinberg Jan 14 '12 at 17:50
I believe the monoid of maps you are looking at is not finitely generated. Also I suspect the second problem you are asking about is undecidable. People in group theory look at the case where there is no 0 and outputs are permuted at each stage and the second question is open in that context. –  Benjamin Steinberg Jan 14 '12 at 17:54

1 Answer 1

This monoid is not finitely generated. Let me prove it for |C|=2. This monoid is residually finite (the action on words by partial functions is length preserving). Therefore the complement of the group of units is an ideal, thus if the monoid were finitely generated the group of units would be too. But the abelianization of this group is the additive group of rational power seres over the 2-element field (see my paper on the ArXiv on testing spherical transitivity) which is infinitely generated.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.