HDTenEightyP/NetNews huggingface dataset:
From: koiran@lip.ens-lyon.fr (Pascal Koiran)
Newsgroups: comp.theory.cell-automata
Subject: decidability and dynamical systems
Date: 11 Sep 92 12:17:18 GMT
Reply-To: koiran@lip.ens-lyon.fr
Organization: Ecole Normale Superieure de Lyon

Hello,

Can someone provide a solution to the following problem, or give references
to related work in the litterature ?

Let f:[0,1]-->[0,1] be a continuous piecewise-linear function (with a finite
number of laps). The endpoints of the laps have rational coordinates.
Given such an f and a rational x \in [0,1], is it decidable whether a fixed
point is reached in finite time when f is iterated on x ?
In other words, is it decidable whether there exists t, f^t(x)=f^{t+1}(x) ?

One can ask the same question for other classes of non-linear functions,
such as polynomials, rational functions, ...
For piecewise-linear functions f:[0,1]^2-->[0,1]^2, the problem is known to
be undecidable.

Thanks,

Pascal.
Newsgroups: comp.theory.cell-automata
From: lange@mathematik.uni-Bremen.de
Subject: image processing
Organization: The Internet
Distribution: inet
Date: Wed, 9 Sep 1992 08:26:34 GMT

Hi !

Does anybody know some good books or articles about image processing
with cellular automata ? Please email me...

Thanks in advance

Ehler Lange
---------------------------------------------------------------------------
| Dipl.-Math. Ehler Lange       | Telefon:	(0421) 218-3539                |
| Universitaet Bremen FB 3      | FAX:     (0421) 218-4236                |
| Centrum fuer Complexe Systeme | E-Mail:  lange@mathematik.uni-Bremen.de |
| und Visualisierung            |                                         |
| Postfach 330 440              |                                         |
| D-2800 Bremen 33              |                                         |
| Germany                       |                                         |
---------------------------------------------------------------------------
Newsgroups: comp.theory.cell-automata
Subject: Thanks to David Bell; life spaceships.
From: wft@math.canterbury.ac.nz (Bill Taylor)
Date: 9 Sep 92 15:36:21 +1200
Distribution: world
Organization: Department of Mathematics, University of Canterbury

David Bell has now posted 2 (actually 3) parts of his massive account of
"Spaceships in Conway's Life".   I, for one, would like to thank him (and
his colleagues) for all this effort.

I have already thanked him by email, and got a slightly mournful reply, that
no-one else had seemed to notice. Certainly I've hardly seen any response
to his spaceship stuff on the list. It can be rather sad to make a big post
somewhere, and get no response, as I know all too well. So, if anyone else
has enjoyed these (and I'm sure there must be *scores* of you), I hope you've
also passed on your thanks and enthusiasm by email.

Big posts like these are the life-blood of a newsgroup, and the spaceship
articles were particularly fascinating. It would be a great pity if David Bell
were to stop sending in his results through apparent lack of interest.
Or anyone else who may have similar results !

So; thanks again, David, and keep up the good work please.
As I say, I'm sure there are many others who want to see it too.
--------------------------------------------------------------------------
           Bill Taylor              wft@math.canterbury.ac.nz 
--------------------------------------------------------------------------
            Humans -  God's attempt to pass the Turing test.
--------------------------------------------------------------------------

Newsgroups: comp.theory.cell-automata
From: borbor@divsun.unige.ch (BORIS Borcic)
Subject: CA on hyperbolic tilings ?
Organization: University of Geneva, Switzerland
Date: Wed, 9 Sep 1992 11:38:54 GMT


Are there results known about CA on hyperbolic grids ?
Do such grids present an interest ?

- Even though I have what I believe to be a clear idea 
of an example, I don't know whether the term 'hyperbolic grid' 
is correct or sufficiently explanatory, and neither do I know
 what is the canonical and concise way to define one, so here
 is the characterization of my example as the next term of 
 a sequence :

                          type         tile         dual tile

tetrahedron               elliptic     triangle     triangle
octahedron                elliptic     triangle     square
icosahedron               elliptic     triangle     pentagon
2D 3gon tiling            parabolic    triangle     hexagon
hyperbolic tiling         hyperbolic   triangle     heptagon
...


Regards,

Boris Borcic
From: u2119737@csdvax.csd.unsw.edu.au
Newsgroups: comp.theory.cell-automata
Subject: FAQ Request
Date: 12 Sep 92 18:22:34 +1000
Organization: University of New South Wales

Is there a FAQ list for this newsgroup?
-- 
 +--------------------------------------------------------------+ 
 |  Malcolm Ryan - U2119737@csdvax.csd.unsw.edu.au              |
 |  Computer Science, University of New South Wales. AUSTRALIA  |
 |                                                              |
 |  "The rest of this quote is..."                              |
 +--------------------------------------------------------------+
From: lordSnooty@cup.portal.com (Andrew - Palfreyman)
Newsgroups: comp.theory.cell-automata
Subject: Re: Thanks to David Bell; life spaceships.
Date: Fri, 11 Sep 92 03:39:49 PDT
Organization: The Portal System (TM)
Distribution: world
  <1992Sep9.122630.18677@crd.ge.com>
  <1992Sep9.102503@twinpeaks.gsfc.nasa.gov>

me too. great post. hope he reads this group :)
	andrew palfreyman
Newsgroups: comp.theory.cell-automata
From: markv@pixar.com (Mark VandeWettering)
Subject: Re: Thanks to David Bell; life spaceships.
Organization: Pixar -- Point Richmond, California
Date: Tue, 15 Sep 1992 18:23:02 GMT


Let me just add my vote too!  Job Well Done!

			Mark T. VandeWettering
Newsgroups: comp.theory.cell-automata
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Crystals in Life
Date: Fri, 11 Sep 1992 20:47:42 GMT
Organization: Security APL, Inc.

I have done some playing around with infinite stable patterns in Conway's
game of Life.  I call such patterns crystals.

(1) Has there been any investigation of this?  A reference would be
appreciated.

(2) I would like to prove that no crystal can have a density greater than
1/2.  1/2 is easy to achieve; just fill space with the rectangle "O." (for
example).  I can establish an upper bound of 6/11 easily enough, but I
haven't managed to do better.
Newsgroups: comp.theory.cell-automata
From: sjouke@izf.tno.nl (Sjouke Burry)
Subject: Re: Thanks to David Bell; life spaceships.
Organization: TNO Institute for Perception
Date: Wed, 9 Sep 1992 09:30:36 GMT

wft@math.canterbury.ac.nz (Bill Taylor) writes:

>David Bell has now posted 2 (actually 3) parts of his massive account of
>"Spaceships in Conway's Life".   I, for one, would like to thank him (and
>his colleagues) for all this effort.

>I have already thanked him by email, and got a slightly mournful reply, that
>no-one else had seemed to notice.


			Hear,hear!!!!!

They worked like a charm when I added them with a little editing to 

my datafile for preset life situations.

So add my thanks , and please continue.

Does anybody know, why traffic is so low here in Holland??

						Sjouke

(P.S. I had to skip the biggest ones ,my limit is 80*60)

*********************************************************************
* Sjouke Burry                           +31 34 63 56426(room phone)*
* TNO Institue for perception            +31 34 63 56211(phone desk)*
*P.O.Box 23                              +31 34 63 53977( fax )     *
* 3769 ZG Soesterberg                                               *
* The Netherlands                                                   *
*                 Email adress: sjouke@izf.tno.nl                   *
*                 Full path   :uunet!hp4nl.nluug.nl!tnosoes!sjouke  *
*********************************************************************

Newsgroups: comp.theory.cell-automata
From: gang@ms.uky.edu (Gang Li)
Subject: question of property of regular set
Date: Mon, 14 Sep 1992 16:50:58 GMT
Organization: University Of Kentucky, Dept. of Math Sciences

I hope this is the correct group to ask this question.
In "Introduction to automata theory, languages, and computation." by Hopcroft
etc, on page 56: "The lemma (pumping lemma) does not state that every
sufficiently long string in a regular set is of the form u(v^i)w for some
large i."
Does this mean there is such a regular set which contains at least one
sufficiently long string which is not of the form u(v^i)w for some large i.
If there is one, can any expert give me an example of it?
Thank you very much!
e-mail prefered.

gang@ms.uky.edu
From: ab@ersys.edmonton.ab.ca (Allan Brockman)
Newsgroups: comp.theory.cell-automata
Subject: thanks david bell
Date: Thu, 10 Sep 92 03:10:46 MDT
Organization: Edmonton Remote Systems #1, Edmonton, AB, Canada

i have never posted to the net befor 
( mostly becous i am dyslexic and this is a text meadyum ) 
but i will use up band width just to convay my thanks.
( i have no mail privilages... ) i have saved your posts and
look foward to more.
                       -allan brockman
p.s. someone port gramatica to the atari-ST...

Allan Brockman              ab@ersys.edmonton.ab.ca
From: shirley@fdr.jsc.nasa.gov (Bill Shirley [CSC])
Newsgroups: comp.theory.cell-automata
Subject: Re: Two questions to life stochastics
Date: 15 Sep 1992 20:30:57 GMT
Organization: Software Technology Branch - NASA/JSC
Originator: shirley@fdr


In article <1992Sep15.153716.10856@unibi.uni-bielefeld.de>, achim@unibi.uni-bielefeld.de (Achim Flammenkamp) writes:
> I have two questions concerning the behaviour or random seeded life areas:
> 
> 1) Assume you have an NxN area seeded with some fixed probability per cell
>    (e.g. 1/3) to alive/death status. There exists the average waiting time T
>    depending on N that the area reaches its "balance configuration". My
>    question is: Does limit T(N) exists if N tends to infinity ? (I think no,
>    but I see no simple argument for my conjecture).

How do you define "balance configuration"?

Stable?  i.e. B(T) = B(T+1)		(where B(N) = Board at time N)
Cyclic?  i.e. B(T) = B(T+c) c>1
	if the board can be broken into non-interinfluencing regions,
	R1 to Rn, that are all cyclic then the board is cyclic.
	c = c(R1) * c(R2) *...* c(Rn)

or

does "balance configuration" allow moving creatures?

do the moving creatures "fall off" the end of the board 
	(to make the board fall into a category above)
	or do they continue infinitely?
asked differently
is the seed NxN or is the board NxN?

on an NxN board, where N is finite, it, of corse, must settle into a cycle.


So, 
  If the board and the seed are infinite, does one escaped glider (can
it escape on an infinely seeded board?) make it "unbalanced"?


> 2) Assume you randomly initialize with fixed probability per cell (e.g. 1/3) a
>    large area. Compare this configuration with the same but changed one cell.
>    Now run both configurations until they reach their "balance configuration".
>    How big is the average area on which these two "balance configurations"
>    differ ? (I think it exists and maybe contain about some million cells).

I don't think there is a limit to the size.
There may be an average size.

what if you "randomly" created an very large fuse?

> 
> achim

curious bill
-- 
Bill Shirley            |  ``Computer Science is not about computers any 
shirley@fdr.jsc.nasa.gov|     more than astronomy is about telescopes.''
From: nelson@rrc.chevron.com (David A. Nelson,Chevron,(510)242-5241)
Newsgroups: comp.theory.cell-automata
Subject: Re: Request for FAQ list
Date: 8 Sep 92 17:44:36 GMT
Reply-To: nelson@rrc.chevron.com
Organization: Chevron, Richmond, California


---
David Nelson
Chevron Research and Technology Company
Nelson@rrc.chevron.com
From: shirley@bush.jsc.nasa.gov (Bill Shirley [CSC])
Newsgroups: comp.theory.cell-automata
Subject: Re: Crystals in Life
Date: 14 Sep 92 14:59:14 GMT
Organization: Software Technology Branch - NASA/JSC
Originator: shirley@bush


In article <1992Sep11.204742.107084@Cookie.secapl.com>, frank@Cookie.secapl.com (Frank Adams) writes:
> I have done some playing around with infinite stable patterns in Conway's
> game of Life.  I call such patterns crystals.
> 
> (1) Has there been any investigation of this?  A reference would be
> appreciated.
> 
> (2) I would like to prove that no crystal can have a density greater than
> 1/2.  1/2 is easy to achieve; just fill space with the rectangle "O." (for
> example).  I can establish an upper bound of 6/11 easily enough, but I
> haven't managed to do better.

Have you investigated how well these crystals can sustain impacts by
moving patterns?  I have always found this interesting, but have not
taken time to study this problem in any depth.

-- 
Bill Shirley            |  ``Computer Science is not about computers any 
shirley@fdr.jsc.nasa.gov|     more than astronomy is about telescopes.''
Newsgroups: comp.theory.cell-automata
From: delusion@casbah.acns.nwu.edu (Albert Schmezer)
Subject: Re: Thanks to David Bell; life spaceships.
Organization: Northwestern University, Evanston Illinois.
Date: Sat, 12 Sep 1992 20:02:55 GMT

In article <1992Sep9.153623.749@csc.canterbury.ac.nz> wft@math.canterbury.ac.nz (Bill Taylor) writes:
>David Bell has now posted 2 (actually 3) parts of his massive account of
>"Spaceships in Conway's Life".   I, for one, would like to thank him (and
>his colleagues) for all this effort.
>

	I really appreciate the spaceships posted on this network. I am in
high school now and have recently developed an interest in CA work...
especially Glider Guns. I would REALLY appreciate any postings on glider guns
or any such phenomena that spawns gliders or spaceships. Thanx alot for you
work! Don't think it has gone unnoticed!

<<delusion
Newsgroups: comp.theory.cell-automata
From: achim@unibi.uni-bielefeld.de (Achim Flammenkamp)
Subject: Two questions to life stochastics
Date: Tue, 15 Sep 92 15:37:16 GMT
Organization: Universitaet Bielefeld

I have two questions concerning the behaviour or random seeded life areas:

1) Assume you have an NxN area seeded with some fixed probability per cell
   (e.g. 1/3) to alive/death status. There exists the average waiting time T
   depending on N that the area reaches its "balance configuration". My
   question is: Does limit T(N) exists if N tends to infinity ? (I think no,
   but I see no simple argument for my conjecture).
2) Assume you randomly initialize with fixed probability per cell (e.g. 1/3) a
   large area. Compare this configuration with the same but changed one cell.
   Now run both configurations until they reach their "balance configuration".
   How big is the average area on which these two "balance configurations"
   differ ? (I think it exists and maybe contain about some million cells).

achim
From: tl@tools.de (Thomas Lewerenz)
Newsgroups: comp.theory
Subject: Re: cute problem regarding finite automata
Date: 05 Sep 92 14:43:52 GMT
Organization: TooLs GmbH, Bonn, Germany
Distribution: inet
NNTP-Posting-Host: fred.tools.de
In-reply-to: johnson@nrtc.northrop.com's message of 4 Sep 92 18:04:00 GMT

In article <40853@gremlin.nrtc.northrop.com> johnson@nrtc.northrop.com (Greg Johnson) writes:
>   Here is a cute problem, perhaps suitable as an exam question.
>   I offer it to all beleaguered professors trying to think up comp
>   questions!  ;-)
>
>   Define a rotation of a string A as follows:  divide A into substrings A1 and
>   A2 such that A1 A2 equals A; A2 A1 is a rotation of A.
>
>   For the string `abcd', the rotations are abcd, dabc, cdab, bcda.
>
>   Now let L be a regular language, and let Rotate(L) be the language consisting
>   of all rotations of strings from L.  Is Rotate(L) regular?  Give proof
>   or counter-example.
>
>   - Greg Johnson
>     johnson@nrtc.northrop.com

I'm not beleaguered nor am I a professor, but here it is:

Let L be a regular language and M be a deterministic finite automaton
accepting L. Let M' be a nondeterministic finite automaton with
eps-moves which behaves as follows:
On input x M' first guesses nondeterministically any of the states of M, say A,
and memorizes it in its finite control. Then it simulates M on input x starting
at state A. Whenever the simulation reaches one of the final states of M, M'
chooses nondeterministically to go on or make an eps-move to the starting state
of M. M' accepts x iff it reaches A on the end of input and has made exactly one
eps-move from a final to the starting state of M during the simulation.
(A more formal description of M' is left to some clever examinee ;-))
Clearly M' accepts x iff x \in Rotate(L) and therefore Rotate(L) is
regular. 
	q.e.d.

--
Thomas Lewerenz, tl@fred.tools.de
Newsgroups: comp.theory
From: dak@kaa.informatik.rwth-aachen.de (David Kastrup)
Subject: Re: Matrix Square Root
Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
Date:  9 Sep 92 16:06:35 GMT

Kevin.D.Brunson.1@nd.edu (Kevin D. Brunson) writes:


>		This is the first message I have posted to this service so I hope that
>this is the most appropriate group.  
>		The problem I have seems like a simple one:  How do I calculate the
>square root of a symetric matrix?  Theoretically, if a matrix A is positive
>semidefinite then there exists a matrix B that is the square root of A such
>that A = B*B.  I have consulted Lancaster and Tismenetsky's "The Theory of
>Matrices" but a programmable algorithm is not obvious.  The matrix I have
>generated in monte carlo experiments is 10 x 10 but I could use a smaller
>one if I could find an operationalization of a method.  
If you do an Eigenvector decomposition A=TDT^{-1}, where D is a diagonal
matrix containg the eigenvalues of the matrix, and T a matrix containing
the corresponding eigenvectors in its columns, TD^{0.5}T^{-1} will
have that property.
From: bevan@cs.man.ac.uk (Stephen J Bevan)
Newsgroups: comp.theory
Subject: Re: Fixed point semantics
Date: 11 Sep 92 20:32:20 GMT
	<1992Sep11.171438.4816@cs.tulane.edu>
Organization: Department of Computer Science, University of Manchester
In-reply-to: fs@cs.tulane.edu's message of 11 Sep 92 17:14:38 GMT

In article <1992Sep11.171438.4816@cs.tulane.edu> fs@cs.tulane.edu (Frank Silbermann) writes:
   If you rely only on continuous operations over continuous
   domains, then how can the semantics be uncomputable?
   Chapter 10 of David Schmidt's text discusses work
   by Uwe Pleban and others on use of denotational semantics
   as an interpreter-generator.

The way I read "Definitional Interpreters" pp 178-183 of Stoy, I get
the feeling that denotational semantics was not meant to be seen as a
route to an interpreter.  In the cases where it is done it seems you
have to take care not to get the fixed pointing wrong, where "wrong"
here means that the fixed point stuff doesn't have unwarranted
assumptions buried in it.  Personally I've always viewed ds
definitions as interpreters, but then maybe that's why I've never got
to grips with the finer points :-)

bevan

@book
{ Stoy77
, author=    {Joseph E. Stoy}
, title=     {Denotational Semantics -- The Scott/Strachey Approach to Programming Language Theory}
, publisher= {MIT Press}
, year=      {1977}
}
From: mwj@rz.uni-jena.de (Johannes Waldmann)
Newsgroups: comp.theory,sci.math
Subject: that signature lemma
Date: 14 Sep 92 22:34:09 GMT
Organization: University Jena, Germany

Some time ago, a signature under a posting in one of these newsgroups
contained a function definition (two lines of C code) and the statement
that this function was total.

I somehow lost that file, so could the originator (or some other friendly
soul who has a copy of it) please send me the text of this lemma again.

Johannes Waldmann

mwj@hpux.rz.uni-jena.de -- currently: jw24@tower.york.ac.uk
From: kemper@moni.informatik.uni-dortmund.de (Peter Kemper)
Newsgroups: comp.theory
Subject: example specification in CCS or CSP
Date: 7 Sep 1992 07:38:23 GMT
Organization: University of Dortmund, Germany
NNTP-Posting-Host: moni

I am looking for example system specifications in Robin Milner's CCS or
C.A.R. Hoare's CSP.
I have found some in R. Milner "Communication and Concurrency" so far
but I am looking for some more to get a better understanding of its
expressiveness and proof/analysis techniques.
Are there any examples of timed CCS?
Please answer by e-mail. Thanks in advance.

Peter Kemper (e-mail: kemper@ls4.informatik.uni-dortmund.de)
From: rose@diku.dk (Mads Rosendahl)
Newsgroups: comp.theory
Subject: Re: Fixed point semantics
Date: 9 Sep 92 06:58:18 GMT
Organization: Department of Computer Science, U of Copenhagen

skow@cs.utwente.nl (Jacek Skowronek) writes:
>What does it mean when "a language gives a least fixed point semantics".

Fixed Point Semantics is often used for the kind of Denotational Semantics 
which is based on Domain Theory and where one does not require the
semantics in some sense to be computable (ie. based on the lambda calculus).

Fixed Point Semantics is used heavily in Abstract Interpretation where neither
the Standard Semantics (often in the form of a Collecting Semantics) or
the Abstract Semantics correspond to lambda terms. They do, however, 
make perfect sense in Domain Theory.

Mads Rosendahl

DIKU, University of Copenhagen, Denmark, <rose@diku.dk>
Newsgroups: comp.theory
From: litow@csd4.csd.uwm.edu (bruce e litow)
Subject: Infinitary codes
Summary: being a `code' w.r.t. omega-strings
Originator: litow@proclus.csd.uwm.edu
Keywords: infinitary codes, omega words
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Date: Thu, 10 Sep 1992 12:13:59 GMT

Litovsky mentions work of Staiger concerning sets of words, R, whose omega
power consists of omega words, each with a unique factorization over R.
It is clear for regular R that this property of being an infinitary code
is decidable. Just express the condition in S1S. But in this case,
especially for finite R, is a better decision method known? One with
an interesting complexity upper bound?

Bruce Litow
Computing Services Division
P.O. Box 413
Univ. Wisconsin-Milwaukee, Milwaukee, WI, 53201
litow@proclus.csd.uwm.edu
From: koiran@lip.ens-lyon.fr (Pascal Koiran)
Newsgroups: comp.theory
Subject: decidability and dynamical systems
Date: 8 Sep 92 09:21:00 GMT
Reply-To: koiran@lip.ens-lyon.fr
Organization: Ecole Normale Superieure de Lyon

Hello,

Can someone provide a solution to the following problem, or give references
to related work in the litterature ?

Let f:[0,1]-->[0,1] be a continuous piecewise-linear function (with a finite
number of laps). The endpoints of the laps have rational coordinates.
Given such an f and a rational x \in [0,1], is it decidable whether a fixed
point is reached in finite time when f is iterated on x ?
In other words, is it decidable whether there exists t, f^t(x)=f^{t+1}(x) ?

One can ask the same question for other classes of non-linear functions,
such as polynomials, rational functions, ...

Thanks,

Pascal.
From: skm8109@usl.edu (Mishra Subhada K)
Newsgroups: comp.theory
Subject: Algorithms for Combinatorial Optimization
Keywords: Optimization, Statistics, Algorithms
Date: 14 Sep 92 03:04:25 GMT
Followup-To: mishra@usl.edu
Organization: University of Southwestern Louisiana

I am looking for references to recent results in the area of combinatorial
optimization techniques that use statistical analysis.
For example, methods based on the theory of extreme order statistics
and/or interval estimate techniques.

 If you know of any publications in realted area, please send me the info
via email.


Subha
(mishra@usl.edu)
From: sri@stan.xx.swin.oz.au (SRITHARAN K)
Newsgroups: comp.theory
Subject: Algorithms in Graph theory
Keywords: MST, Steiner Tree, Shortest Path
Date: 15 Sep 92 03:58:31 GMT
Organization: Computer Centre, Swinburne University of Tech., Melbourne, Australia.


My research is finding efficent way of allocating multicasts in tele-
communcations network under BISDN. I wish if some of you can provide
any alogrithm written in C for finding spanning trees for specific subset
of nodes in a graph, finding shortest path between all nodes and steiner
tree algorithms.

Thanks

Sri
(sri@stan.xx.swin.oz.au)
Newsgroups: comp.theory