HDTenEightyP/NetNews huggingface dataset:
From: jbaez@riesz.mit.edu (John C. Baez)
Subject: Re: fractal inversion & perpetual motion
Organization: MIT Department of Mathematics, Cambridge, MA
Distribution: inet
Date: Wed, 27 Jan 93 02:54:06 GMT

I was interested to read the ad for the Barnsely/Hurd book on
fractal-based image compression and Jordan Pollack's skeptical reply.  
I too would be fascinated to hear from anyone who has bought the book.
For those who aren't familiar with the story... Barnsely (and I guess
Hurd, though I don't know) have greatly hyped an approach to data
compression for visual images that relies on fitting an iterated
function system (which produces a fractal) to an image.  They have
apparently claimed compression factors far beyond what normal techniques
achieve, and demonstrated this to the defense department.  Now, one can
very easily run an iterated function system and get a fractal image.
I'm sure many of you have seen the very nice picture of a fern one can
get this way.  But the question is, can *most* images be fit well by
fractals?  And more importantly, as Pollack points out, can the fitting
be done automatically?  Barnsely and Hurd seem to claim so... but they
have never described how they would do so.  In fact, Barnsely refused to
tell Steve Wolfram (of Mathematica fame) how the trick works, and said
he didn't patent the method, because patenting it would give the secret
away.  This irritated Wolfram, because it implicitly assumed that nobody
else was smart enough to figure out how this "fractal transform" from
images to iterated function systems works.  Wolfram jokingly said
(later) that he should figure out the trick and reveal it, just to spite
Barnesly.  I heard about all this (through channels who will remain
anonymous), and I tried to figure out the trick myself and failed.  (I didn't
try very hard, though, and this sort of thing is not my specialty; I'm
just a mathematical physicist who knows analysis pretty well.)  Now it
seems that more and more people are thinking there IS no trick - i.e.,
that the whole thing is a scam.  

So - does anyone out there know more about this business?  I have no
desire to make big bucks in the image compression business.  It just
seems to me that if there IS a "fractal transform," it might be a very
beautiful piece of mathematics, and should not be sitting in some safe
marked "TOP SECRET".
From: butterwo@cs.unc.edu (Jeff Butterworth)
Newsgroups: comp.theory.cell-automata
Subject: Re: ftp locations of lattice gas software
Date: 27 Jan 1993 13:00:11 -0500
Organization: The University of North Carolina at Chapel Hill
Distribution: inet
NNTP-Posting-Host: gamella.cs.unc.edu

In article <1993Jan26.235136.17364@gowron.harvard.edu> eliot@head-cfa.harvard.edu (Eliot Shepard) writes:
>does anyone know where I can find software that runs 2- or 3-D lattice
>gas fluid simulations on a PC or Sun? also, would anyone who is up-to-date
>on this topic point me to a reference describing the state of the art?
>

It's good to see some interest in CA's for use in fluid simulations.
I almost thought everyone had forgotten about it.  Here are some references
to what I consider to be some of the clearest and implementation oriented
papers.

LGA == Lattice Gas Automata (bit twiddlying methods, noisy)
LBA == Lattice Boltzmann Automata (floating point methods, more sophisticated)


"Cellular-automaton fluids:  A model for flow in porous media"
Daniel H. Rothman
Geophysics, Vol. 53 (1988) p. 509

Comments:	This is an excellent introduction to 2D LGA and some simple
		applications.


"Lattice Gas Models for 3D Hydrodynamcs"
D. D'Humieres, P. Lallemand and U. Frisch
Europhysics Letters, Vol. 2  No. 4, pp. 291-7 (1986)

Comments:	Good paper on 3D LGA.  They present 19 bit and 24 bit models.


"The Lattice Boltzmann Equation:  A New Tool for Computational Fluid-Dynamics"
Sauro Succi, Roberto Benzi and Francisco Higuera
Physica D, Volume 47, (1991) pp. 219-230

Comments:	This is a fairly general presentation of the linearized
		collision operator for the LBA method.  Quite a few
		applications are presented.


"Lattice Boltzmann model of immiscible fluids"
Andrew K. Gunstensen and Daniel H. Rothman, Ste(')phane Zaleski,
Gianluigi Zanetti

Comments:	Very well written.  Explains the linearized collision operator
		for LBA very succinctly.  Includes rest particles to guarantee
		galillean invariance.


"Lattice Boltzmann Computational Fluid Dynamics in Three Dimensions"
Shiyi Chen, Zheng Wang, Xiaowen Shan, and Gary D. Doolen
Journal of Statistical Physics, Vol. 68  Nos. 3/4, Aug. 1992

Comments:       Pretty good paper describing 3-D LBA.  The LBA model is
		simpler than the linearized collision operator used in
		the early papers.  The model has only 14 directions in 3-D,
		which is much better than the 24 normally needed.
From: wbdst+@pitt.edu (William B Dwinnell)
Newsgroups: comp.theory.cell-automata
Subject: Re: I saw these really colourful cellular automata - what are they?
Date: 22 Jan 93 23:17:03 GMT
Organization: University of Pittsburgh


That looks like wireworld, as long as the background '.xxx ( "."s, in 
your diagram) are all in the 'wire' state, and the tails are always
behind the direction of motion.
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.theory.cell-automata
Subject: Re: cellular automata with different rules at each site
Date: 22 Jan 93 12:04:39 GMT
Organization: Department of Computer Science, U of Copenhagen

demaris@austin.ibm.com (Dave Demaris) writes:


>These are called inhomogeneous cellular automata.

I would expect that any automaton with a finite set of different rules
for different sites can be simulated by a uniform automata with a
somewhat larger state-space.

A simpe example is wire-world. It can be seen as having different
rules for background cells (one possible state) and wire cells (three
possible states), but usually it is implemented as a single type of
cell having four possible states.

It can, though, be easier to describe an automaton as having several
types of cells with each their state space rather than a single type
of cell with a huge state-space.

A truly inhomogenous automaton (which can't easily be simulated with a
uniform automaton) is one where each cell is not connected to it's
nearest neighbours but to arbitrary other points. If there is no limit
to the distance, there is no obvious way to reduce this to a uniform
grid. In a similar vein one could imagine an automaton on a
non-periodic Penrose tiling. Using the variant with two rhombic tiles,
each will have four neighbours, so the rules for each cell could be
identical, but the global behaviour would be non-uniform.

	Torben Mogensen (torbenm@diku.dk)

 
Xref: sparky comp.theory.cell-automata:634 sci.fractals:645
From: wbdst+@pitt.edu (William B Dwinnell)
Newsgroups: comp.theory.cell-automata,sci.fractals
Subject: Re: fractal inversion & perpetual motion
Date: 27 Jan 93 03:43:51 GMT
Followup-To: comp.theory.cell-automata
Distribution: inet
Organization: University of Pittsburgh


I don't know what sort of performance figures you have heard, but fractal
image compression is for real. It is quite amazing, actually, to
see it in action. It is my understanding that fractal graphics compression
schemes are typified by long compression times (yes, searching for
the fractal "patterns" is a pain), quick decompression, and excellent
compression ratios.  The matter of image degradation vs. other
compression systems (like JPEG), has not been clarified to me.
From: GRS00042@CONRAD.APPSTATE.EDU (Dov Sherman)
Newsgroups: comp.theory.cell-automata
Subject: CA-Lab for PC by FTP?
Date: 23 Jan 1993 22:10:57 GMT
Organization: APPALACHIAN STATE UNIVERSITY
Distribution: world
NNTP-Posting-Host: stat.appstate.edu
X-News-Reader: VMS NEWS 1.24

I'm looking for a CA-Lab for PC's which I can get by anonymous FTP.
Particularly I'm looking for something that will allow me to
save, load, magnify, and maybe even allow me to edit/create the rules
for an automaton rather than simply using one of the standards.
Is anyone aware of such a program available by FTP?

--- Dov Sherman
    grs00042@stat.appstate.edu
From: michaelr@spider.co.uk (Michael S. A. Robb)
Newsgroups: comp.theory.cell-automata
Subject: I saw these really colourful cellular automata - what are they?
Date: 22 Jan 93 18:44:10 GMT
Organization: Spider Systems Limited, Edinburgh, UK.


  While sorting out my collection of video-taped programmes, I came 
across one of those weekly science programmes (Equinox) which was 
covering Cellular Automata. 

Several guest-stars on the programme were Bill Joy (who was running
genetic-algorithms on a Connection Machine) and some MIT researchers
describing how they managed to decode the algorithm used by ants to
decide which direction to move in.

Of particular interest to my were several very colourful "life"-like
algorithms which seemed to have cells with more than 2 states. The
first algorithm seemed to have three different states and had cells
which could move in the following pattern:

   1       2        3       Generation
........ ........ ........
..*@.... ...*@... ....*@..  These shapes seemed to be able to move in
...*@... ....*@.. .....*@.  any of four directions.
...*@... ....*@.. .....*@.
........ ........ .......

Another algorithm seemed to be able to handle a universe with 256  
different states of cell, with the colony growing until the entire
universe was occupied. Then the screen would seem to colour cycle in
a swirling pattern. 

Does anyone know what algorithms are being used and/or any references
I could check up?

PS. Did MIT ever publish the algorithm that ants use to move around?

Cheers,

  -- Michael
-- 
| Michael S. A. Robb     | Tel: +44 31 554 9424  | "..The problem with bolt-on
| Software Engineer      | Fax: +44 31 554 0649  |  software is making sure the
| Spider Systems Limited | E-mail:               |  bolts are the right size.."
| Edinburgh, EH6 5NG     | michaelr@spider.co.uk |             - Anonymous
From: jf41+@andrew.cmu.edu (Jonathan R. Ferro)
Newsgroups: comp.theory.cell-automata
Subject: Re: I saw these really colourful cellular automata - what are they?
Date: 25 Jan 93 06:58:47 GMT
Article-I.D.: andrew.4fN1l7200VokQ6fopU
Organization: Carnegie Mellon, Pittsburgh, PA

michaelr@spider.co.uk (Michael S. A. Robb) writes:
>    1       2        3       Generation
> ........ ........ ........
> ..*@.... ...*@... ....*@..  These shapes seemed to be able to move in
> ...*@... ....*@.. .....*@.  any of four directions.
> ...*@... ....*@.. .....*@.
> ........ ........ .......
>
> Does anyone know what algorithms are being used and/or any references
> I could check up?

This is a rule called "neurons" in the Toffoli and Margolis book.  The
rule is that "resting" (.) goes to "firing" (@) if exactly two adjacent
cells of the eight are firing (@).  Firing (@) always goes to
"refracting" (*), regardless of neighborhood (note difference from the
wireworld rule), and refracting (*) always goes to resting (.)
regardless of neighborhood.  The names of the three states are taken
from neurophysiology, as the requirement of a refractory period is
intended to simulate neuronal activity.

This rule is especially fun to watch in a large wraparound (toroidal)
field starting from a relatively sparse random filling.

-- Jon Ferro               Einsprachigkeit ist heilbar
Newsgroups: comp.theory.cell-automata
From: andy@extro.ucc.su.OZ.AU (Andrew Miehs)
Subject: Wire World?
Organization: Sydney University Computing Service, Sydney, NSW, Australia
Date: Tue, 26 Jan 1993 09:02:05 GMT

I am interested in getting this "Wire-World" program which has been mentioned
a lot recently. Is it available for the Macintosh? If not, how about a PC
version?


-- 
+-------------------------------+---------------------------------------------+
| Andrew Miehs                  |                                             |
| Mail: andy@extro.ucc.su.oz.au |       $$$ THIS SPACE FOR RENT $$$           |
| NB:   Don't call me andy!     |                                             |
Organization: University of Haifa - Mt. Carmel Haifa, Israel.
Date: Monday, 25 Jan 1993 15:45:49 IST
From: Dan Gordon <RSMA410@HAIFAUVM.BITNET>
Newsgroups: comp.theory.cell-automata
Subject: Re: cellular automata with different rules at each site

In article <105853@netnews.upenn.edu>, bill@amy.med.upenn.edu (Bill Tozier)
says:
>  Is anyone familiar with any work that's been done with
>cellular automata in which the rules for any given cell are fixed,
>but may be different for different cells? I'm currently looking
>(on the back of an envelope, literally) at behavior of 1D, neighborhood-3
>2-state automata when each cell has a random rule table. Without
>much stretching, this type of automaton would seem to be a re-description
>of a class of networks that includes Boolean nets (a research
>specialty in these parts).

It's not clear what you mean by "random rule table".  This can be
interpreted as a probabilistic automaton.  It can also be interpreted
as meaning that in every cell, the rule table is fixed (and not
probabilistic), but the choice of which rule table goes in which
cell is random.  A consequence of this is that more than one rule
table can appear infinitely many times in the initial configuration.

Assuming you are referring to the second possiblilty, the answer is
simple:  There are only 256 such rule tables (or transition functions)
so your automata can be simulated by homogeneous automata with 512
states, in which the initial configuration is chosen randomly and
infinitely many cells may be in a non-quiescent state.

Further explanations:  a rule table (in the type of automaton that
you use) is a function from the set of all triples of 0,1 to the
set {0,1}, and there are 256 such functions - call them T_1...T_256.
The homogeneous automata that will simulate these will have states
of the type (A, i), where A is in {0,1} and 1 <= i <= 256; a total
of 512 states.  The rules for the homogeneous automata are as follows:

If a cell is in state (A, i), its left neighbor in state (B, j),
and its right neighbor is in state (C, k), then simply apply rule
T_i to the 3-neighborhood B-A-C.  Suppose rule T_i changes state A
to state D, then the simulating automaton should change the current
state (A, i) to state (D, i).  Note that i does not change.

The simulation is now straightforward:  a cell in state A, having rule
table T_i is simply simulated by a homogeneous automaton in state (A, i).

The usual assumption in cellular automata is that in the initial
configuration, all but a finite number of cells are in a special state
called the "quiescent state".  However, in your automata, you allow
more than one rule table to appear infinitely many times, so the
simulating automata must also be allowed to have more than one state
appear infinitely many times.  I believe this has been looked at
in the literature, but I have no references available.

Dan Gordon.
From: eliot@head-cfa.harvard.edu (Eliot Shepard)
Newsgroups: comp.theory.cell-automata
Subject: ftp locations of lattice gas software
Date: 26 Jan 93 23:51:36 GMT
Organization: Smithsonian Astrophysical Observatory, Cambridge, MA,  USA

does anyone know where I can find software that runs 2- or 3-D lattice
gas fluid simulations on a PC or Sun? also, would anyone who is up-to-date
on this topic point me to a reference describing the state of the art?

thanks!

Eliot Shepard

-- 
  |\    |\
  | \   | \ 		yeah, i stole this from someone
  |  \  |  \
  |   | |  |
From: andreas@phoenix.ims.uni-stuttgart.de (Andreas Eisele)
Newsgroups: comp.theory
Subject: Recent work on parsing with probabilistic CFGs ?
Date: 26 Jan 1993 04:22:56 GMT
Organization: IMS, University of Stuttgart, Germany
Distribution: world
Reply-To: andreas@ims.uni-stuttgart.de
NNTP-Posting-Host: phoenix.ims.uni-stuttgart.de

I am looking for recent papers on that topic. I know the papers by
Wright, Wrigley & Sharman and by Ng & Tomita in the IWPT 91
proceedings, but nothing that has been done or published since.

In particular, I'm wondering if anyone has tried to come up with a
probabilistic version of a parser for general CFG in the style of
Earley 70,  and Graham, Harrison & Ruzzo 80. If you have tried and
have encountered results or unexpected difficulties, I would be very
interested in knowing about them.

Thank you very much in advance for any information

Andreas Eisele
--
+--------------------------------------------------------------------------+
|Andreas Eisele          Inst. f. Logik, Komplexitaet u. Deduktionssysteme |
|Tel.:    +49-721-608-4734     Universitaet Karlsruhe, Am Fasanengarten 5  |
|Fax.:    +49-721-60 77 21   D-7500 Karlsruhe 1,  Fed. Rep. of Germany     |
|email:   andreas@ims.uni-stuttgart.de, eisele@ira.uka.de    (NeXTMail ok) |
+--------------------------------------------------------------------------+
From: hinrichs@math.uni-muenster.de (Klaus H. Hinrichs)
Newsgroups: comp.theory
Subject: FOCS '93
Date: 28 Jan 1993 13:10:42 GMT
Organization: Westf. Wilh.-Universitaet Muenster, Germany.
Distribution: world
Reply-To: hinrichs@math.uni-muenster.de
NNTP-Posting-Host: boole.uni-muenster.de

Does anyone have any information about when and where FOCS '93 will take place?
Has there already been a call for papers?

Klaus H. Hinrichs
e-mail: hinrichs@math.uni-muenster.de


Xref: sparky comp.theory:2932 sci.crypt:7159 rec.puzzles:8569
From: fischer-michael@cs.yale.edu (Michael Fischer)
Newsgroups: comp.theory,sci.crypt,rec.puzzles
Subject: Re: Generating a Random Permutation
Date: 26 Jan 93 17:01:51 GMT
Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
Followup-To: comp.theory,sci.crypt,rec.puzzles
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
X-Newsreader: TIN [version 1.1az (for az) PL8]

Stephen Bloch (sbloch@silver.cs.umanitoba.ca) wrote:
: sumner@math.scarolina.edu (David Sumner) writes:
: >> In an earlier post I wrote that an easy way to generate a
: >> random permutation of the integers 1-n was:
: >> >      ++++++++++++++
: >> >  Initialize  A[n] as the array [1, 2, 3, 4,..., n]
: >> >        for i=1 to n
: >> >        z = random(n)
: >> >        t = a[i]
: >> >        a[i] = a[z]
: >> >        a[z] = t
: >> >        next i
: >> >    ++++++++++++++
: >> There is a typo in this. The line 'z = random(n)' should
: >> be 'z = random(i)'

: I THINK (but am not sure) the
: corrected one is also incorrect, for the reasons Thomas states.

The corrected algorithm can be seen to be correct by a simple
inductive argument.  Namely, after the i-th iteration, A[1]...A[i]
contains a random permutation of 1,...,i, and A[i+1]...A[n] contains
the numbers (i+1),...,n in sequence.  The next iteration swaps A[i+1]
= (i+1) with a randomly-chosen A[z], where 1 <= z <= i+1.  Thus, (i+1)
is equally likely to go into any of the first i+1 slots, and the
remaining positions end up being filled with a random permutation of
1,...,i.  This results in a random permutation of 1,...,i+1 as
desired.

Since the induction hypothesis is obviously true for i=0, it holds for
all i<=n by induction.  Thus, after the last iteration, A[1],...,A[n]
contains a random permutation of 1,...,n.

==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================
Xref: sparky comp.theory:2922 comp.lang.prolog:2440 comp.lang.functional:1552 sfnet.tiede.tietotekniikka.tohtorix:36
From: desj@ccr-p.ida.org (David desJardins)
Newsgroups: comp.theory
Subject: Re: solution or information needed
Date: 28 Jan 93 01:01:23 GMT
Organization: IDA Center for Communications Research, Princeton

Charles C. Lin <clin@eng.umd.edu> writes:
>>	The language {ww|w E (0 + 1)*} is
>>	(A) not accepted by any Turing machine
>>	(B) accepted by some Turing machines, but by no pushdown automata
>>	(C) accepted by some pushdown automaton, but not context-free
>>	(D) context-free, but not regular
>>	(E) regular

> I recently took the CS GREs, and questions like this do not seem to
> be as prevalent.   While I won't say the entire test is easy, because
> it's not, they do seem to have made somewhat more reasonable questions.

Does any other reader of this newsgroup want to defend the proposition
that this is an "unreasonable" question??  This is about the easiest
nontrivial question one could pose on the theory of computation; either
this question is perfectly reasonable, or there is no need for theory,
and thus for this newsgroup.

                                        David desJardins
From: naylor@research.canon.oz.au (William Naylor)
Subject: simulated annealing question
Organization: Canon Information Systems Research Australia
Date: Wed, 27 Jan 1993 00:45:39 GMT

I am trying to minimize a real-valued function of about 50-500 real-valued
variables.  My function seems to have an exponential number of local minima,
so I have been trying to adapt SIMULATED ANNEALING to work on functions of
continuous variables.  Classically, simulated annealing [1] is designed to
work on discrete functions, with discrete domains.

Has anybody out there successfully used simulated annealing 
on continuous functions with continuous domains?  I would appreciate 
any advice, especially with references.  


REFERENCES

[1]  Kirkpatrick S., Gelatt C. D., and Vecchi M. P.: "Optimization by
     Simulated Annealing", Science 1983, #220, pages 671-680.



-- 
Will Naylor               net:  naylor@research.canon.oz.au
                          mail: Canon Information Systems Research Australia  
phone: (61-2) 805-2921          P.O. Box 313 North Ryde, NSW 2113 
fax:   (61-2) 805-2929          Australia
From: robg@wsinti03.info.win.tue.nl (Rob Gerth)
Newsgroups: comp.theory
Subject: Lecture of prof. Shmuel Katz
Date: 22 Jan 93 10:29:01 GMT
Reply-To: robg@info.win.tue.nl
Distribution: eunet
Organization: Eindhoven University of Technology, the Netherlands


Computer Science-colloquium, Technical Univeristy Eindhoven.




Speaker:          prof. Shmuel Katz
                           (Technion, Haifa, Israel)
Date:            monday February 1st, 1993
Time:                      13.30
Place:           CTD 131, Technical University Eindhoven, Holland
Subject:        Superimposition as a language construct

                           


Abstract:

Several versions of a language construct called a superimposition have been
proposed. They are intended to allow easy expression of modules that add
functionality to a distributed system but require access to the state of the
existing processes and execute interleaved with the rest of the computation.
Examples are modules for additional monitoring of existing processes,
debugging aids, repeated checking of whether deadlock has occurred,
increasing fault tolerance, or introducing buffers to reduce synchronization
of processes.    
These constructs capture a kind of modularity natural for distributed
programming, which previously has been treated using a macro-like
implantation of code. In the talk, the elements of a superimposition are
identified, the various options for definitions are compared, correctness
criteria are defined, and examples are presented. A key question is the
degree to which the superimposed code is allowed to affect the values of
variables in the original program, and the influence this has on the safety
and liveness properties that held in the program without the
superimposition.  



-- 
# internet:     robg@win.tue.nl         | Rob Gerth		              #
# EUT:		HG 8.85			| Department of Computing Science     #
# voice:	+31-(0)40-474389/4124	| Eindhoven University of Technology  #
# fax:		+31-(0)40-463992	| 5600 MB Eindhoven, The Netherlands  #