Thanks for sharing the bib search results. There seems to be about a 10
year gap between the
2 sets of papers as well as some shift in field.
The linear algebra papers would have to have some pretty heavy-duty
simplifications before I would be
inclined to pay any attention to Milstein's opinion on primality testing.
About 20 years ago, I took a couple
of courses from John Rhodes at UC Berkeley on finite state machines (Rhodes
called it Automata Theory).
Basically, any finite state machine can be decomposed as a semi-direct
product of finite groups and
(perhaps several copies of) one very elementary semi-group
U3, three elements 1,x,y: 1 is the identity and xy = y and yx = x.
(Forgets left argument.)
Now, from back in the 60's, any finite group can be represented in matrices
-- lots of ways. If U3 can be represented
by linear algebra (exercise for the reader), this seems to complete the
case for finite state machines -- in very vague terms.
Again, I hope there is something a wee bit deeper than fleshing out this
general approach, then I remain unimpressed.
What would impress me? Something along the lines of Rapheal Robinson's
results on spheres: the Bolzano-Tarski
theorem proved (what, back in the 1920's?) that you could cut a solid 3D
sphere into finitely many chunks, then rearrange
the chunks to make another solid (no holes or gaps) 3D sphere with _twice_
the volume. Pretty spooky, I always felt.
Robinson first proved that 9 chunks would do it. Then he found a way with
5 (maybe it is 4) and I think he showed that this
was the minimum.
The linear representations of finite state machines is at first blush a
"fairly" straightforward application of
linear representations of finite groups and the decomposition theorem for
finite state machines. Is there
some real content?
Message text written by INTERNET:[EMAIL PROTECTED]
>* Moeller TL, Milstein J
Generalized algebraic structures for the representation of discrete systems
LINEAR ALGEBRA APPL 274: 161-191 APR 15 1998
* Moeller TL, Milstein J
Algebraic representations for finite-state machines .2. Module formulation
LINEAR ALGEBRA APPL 247: 133-150 NOV 1 1996
* Moeller TL, Milstein J
Algebraic representations for finite-state machines .1. Monoid-ring
formulation
LINEAR ALGEBRA APPL 239: 109-126 MAY 1996
<
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
