Vladimir Z. Nuri wrote:
>
> Nico-- I don't understand everything you're referring to
> but have a rough intuitive understanding of what you
> are trying to accomplish. one question:
>
> > This is where semigroups come in (a generalization of groups, which
> >only model state- permutations, while semigroups model transformations
> >of a set Q: several states may map under one input onto the same next
> >state, which is not allowed in a permutation!).
>
> this almost sounds like you are referring to NFA's, nondeterministic
> finite automata? if not, how is what you are referring to different?

No, a state transform a: Q --> Q (state-change of a SM to input 'a')
is a function, so its value (in codomain Q) is uniquely determined
for every present state (argument in the domain, also Q). So I am
talking about DFA: Deterministic Finite Automata (= FSM: Finite State
Machines). In fact they are formally equivalent: what one type can
do, the other can also, although at first this seems strange.

So you can, under one input 'a', have many-to-one mapping of states,
(DFA) but not a one-to-many mapping (NFA). The NFA type can be
transformed to a DFA by expanding the input set A, to give each
"branch" of a many-to-one state transition its own input {a1, a2, .. an}

> I was in a complexity class in which the professor spent a whole
> day going over a pretty rudimentary algorithm to minimize a DFA,
> not very elegant. (there is a n log n version in terms of states,
> however, but he didn't give this version). it's the version given
> in Hopcroft and Ullman. I asked him if there was an algorithm
> to minimize a NFA, and he never did seem to know the answer.
> it seems like an obvious question, but I am not aware of a
> reference. I'm sure there is an elegant algorithm for an
> NFA, and I bet I could find it if no one has yet. I did find
> a n log n DFA minimization algorithm that is fairly elegant.
>
> I wonder if you are in fact trying to minimize NFA's. when
> you said in another part you need something that takes into
> account the complexity of the "next state" function, that
> sounded a lot like NFA minimization.

No, it is in fact unwise to minimize # States, because what
matters for a decomposition into two smaller machines, with one
possibly coupled to ('controlling') the other 'dependent'
machine, is a "preserved state partition" -- Which may be there
all right, but can be "destroyed" by too much state compression,
as it were.

This concept of "preserved state partition" is crucial to the
inherent structure a machine can have. So I'll spend some effort
here to explain. (For math intimi: it's like a congruence).

Assume we have machine M(Q,A): Q x A --> Q (stateset Q, inputset A).
And we want to 'split' or decompose it into two smaller machines
M1(Q1, A1) ==> M2(Q2, A2) where A = A1 x A2 and Q = Q1 x Q2 are the
corresponding 2-component decompositions ('direct product') of the
inputset and stateset, respectively. Notice the "coupling" ==>
between them, meaning that the next state of M2 depends not only on
its own present state & input (Q2, A2) but *also* on the state in
Q1 of the "leading" component M1.

This coupling is e.g. modeled by a combinational function like
F12: (Q1,A2) --> A" which maps Q1 and external inputset A2 into
input component A" of M2.
Cascade coupled pair of machines
So we get: A1 A2 M1 = leading, M2 = dependent
| | (independent) machine.
V V
+----+ Q1 | +----+
| M1 |-o->|\_A"__| M2 |--o--> Q2
|____| | |/ |____| |
|____V F12 |_____V

I hope this cripple drawing makes sense;-)
Coupling function F12 is the enlarged triangle arrow
from (Q1,A2) --> into A"
Now the possibility of such "factoring" of M = M1 * M2 into
two casded machines, depends on there being a partition P1 of Q
such that: each part of Q maps under each input of A into just
one part of Q again. We say: such state partition P1 (disjoint union
of parts that covers Q) is "preserved" under every input 'a' in A.

If that is the case, then consider the parts of P1 as stateset Q1.
Clearly the next-state (= Q_part) of M1 dependens then *only* on
its present state (= Q_part) and input in A, and *not* on the state
(in Q2) of M2. Notice that Q2 must then also be the set of parts of
a partition P2 of Q, but which is "orthogonal" on the parts of P1.
This means that each state of Q is in precisely one part of P1 and
in one part of P2, hence identified by two state components (Q1,Q2).

If, by chance, partition P2 can be found which is *also* preserved
under A, then apparently M2 is also an independent component of M.
Hence we found a both-way independent decomposition M = M1 x M2,
also called a direct product (no coupling). Inputset A has derived
partitions that yield two input components A1 and A2.

What has this to do with the sequential closures S1 = (A1)*/Q1 and
S2 = (A")*/Q2 ? Well, it follows readily that such decomposition
exists whenever semigroup S = A*/Q has an image S' which in fact
is (isomorphic to) S1. Denote this by divisor S1 of S: S1 | S.
Meaning: S has a partition (=congruence) that is preserved under
the operation of the semigroup (= input sequencing).

The smallest divisors (smallest leading machines) ever possible
have a closure (semigroup) that has no proper congruence (no non-
trivial preserved partition). To be called "prime" semigroups,
and "prime" state machines PSM. They are either the semigroups
of order 2 (of which there are five non-isomorphic), or the
infinite class of prime cycles Cp, including C2 of course,
extended with the (infinite) class of "simple groups" which are
apparently defined as groups without a proper congruence (= no
proper normal subgroup, for the intimi;-)

Shall I leave it at this? I hope this made sense to you, and if
I was unclear at some point(s), please let me know. More detail
is useless now, if you missed a clue.

> Question: so you are decomposing some kind of FA's into rudimentary
> FA's for your circuits. why is it necessary to do this? why
> not just encode the FA's in the circuitry instead of hunting
> for "building block" decompositions of them?

What I am after is not just one practical binary encoding of
a given next-state table, but I use semigroups (seq-closure of
a state machine) as a conceptual tool to get at its "natural"
(possibly cascade) structural decomposition. Cascade is nice for
testing purposes: start testing the leading machine, because its
behaviour does not (by definition) depend on the rest! And repeat
with the more dependent machines ( >2 components by recursion!).

Also software can have such structure, and if cascade decomposable:
it has a clear top-down hierarchy, which is cycle-free in its coupling
(dependency) structure. Notice also there commutative semigroup can
always be decomposed as a (sub-semigroup of) a direct product, hence
coupling_free! And non-commutativity translates in machine structure
as requiring coupling! --- We also see that *only* a "simple_group"
permutation machine, that is a "prime" machine without congruence,
has no cascade decomposition. Hence *must* be decomposed by using
subgroups (of which there are plenty, but *no* impages -- hence no
normal subgroups) in a non-cascade fashion, say a cyclic coupling
pattern (?) as easiest alternative. (nec & suff?)

> {....} It would be helpful for me, and perhaps others on the list,
> if you care to, to state the definition of a semigroup or group,
> then the definition of the FA, then show how they are equivalent
> somehow..

See above explanation ;-)

> Also, when referring to your papers on a web site, please include a
> complete URL if possible ... this will help whoever is looking
> for your paper.

ref[2] on my homepage: "The structure of Constant Rank State Machines"
http://www.iae.nl/users/benschop/c-ranksm.dvi

Ciao, Nico Benschop. | AHA: one is Always Halfway Anyway
http://www.iae.nl/users/benschop | xxxxxxxxxxxxxxxx.xxxxxxxxxxxxxxxx

____________________________________________________________
List Site: http://www.findmail.com/list/theory-edge/
To unsubscribe, send to theory-edge-unsubscribe@...

FREE group e-mail lists at http://www.findmail.com