2
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\begingroup$ Cross-posted at scicomp.stackexchange.com/questions/697/… $\endgroup$
    – JRN
    Commented Jan 14, 2012 at 2:41
  • $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 14, 2012 at 12:39
  • $\begingroup$ Domain of is every pair of (input channel, internal state), range is some subset of this, we transition to the state f(c,s). $\endgroup$
    – knotted
    Commented Jan 14, 2012 at 12:53
  • $\begingroup$ But by your description f has images pairs, so not a state. Or are you sending it to the pair (outpu,next state). $\endgroup$
    – Benjamin Steinberg
    Commented Jan 14, 2012 at 17:50
  • $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Commented Jan 14, 2012 at 17:54

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .