# Composite finite-state machines

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?

-
Cross-posted at scicomp.stackexchange.com/questions/697/… –  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
show 1 more comment