HDTenEightyP/NetNews huggingface dataset:
From: peter@FWI.UVA.NL (Peter van Emde Boas)
Newsgroups: comp.theory
Subject: Re: Are there reductions from Hilbert's 10th problem?
Date: 1 Sep 92 23:03:13 GMT
Reply-To: Peter van Emde Boas <peter@fwi.uva.nl>

Dear Imre. I know of a prime example of a reduction from Hilbert 10
which in the mean time seems to have been replaced by a far easier
reduction by direct means.

The reference is to be found in the ph.d. thesis of Jan van Leeuwen, Rule
labeled programs, written under prof. D. van Dalen  on which he graduated
jun 07 1972.

As told the same problem, dealing with the generative power of some
specific class of controled context free grammars, nowadays can be
solved directly in a few pages instead of the ca. 50 pages in this
thesis. Still it is an example of the sort of reductions you seem to
be looking for.

Sincerely yours
Peter van Emde Boas
From: gupta@nmsu.edu (Gopal Gupta)
Newsgroups: comp.theory
Subject: Logic Programming as an Introductory Programming Paradigm
Date: 26 Aug 92 15:47:23 GMT
Organization: NMSU Computer Science


		       Call for Participation

		Logic Programming as an Introductory
			Programming Paradigm

		Informal Birds-of-a-Feather Session
		
		Joint International Conference and 
		Symposium on Logic Programming '92

		      Tuesday, Nov 10th, 1992
			   6:00PM -- 8:30PM

		  Organizers: J. Reinfelds and G. Gupta

This informal session is  devoted to  discussion on  using  the  logic 
programming  paradigm to teach programming to beginners. The  emphasis 
is on  teaching  logic  programming (rather than Prolog), and  the aim 
is to induce beginners to learn ``declarative thinking." This approach 
can be  contrasted with  the functional programming  approach that has 
been becoming increasingly popular recently.

The discussion  is open to  all the participants in the conference who 
are  invited  to present  their  views on  (but  not  limited  to) the 
following issues:

1) Why is  Logic  Programming  a  more  suitable paradigm for teaching 
	programming to beginners?
2) Is there a need for  using LP for this purpose, or is FP enough, or
	is some other approach better?
3) How to evaluate the success of such an enterprise?
4) Your  experiences  related  to  using  LP  to  teach programming to
	beginners.

Dissenting views are specially welcome.  

As part of the session  we will  relate our  experience  with using LP 
(and a closely co-ordinated  sister course in discrete Math and Logic) 
to teach programming to Freshman students  at New Mexico State. Others 
are welcome to relate their experiences too. 

Please note  that the primary focus of the session will be on teaching 
logic programming to beginner programmers. Discussion related to teach-
ing Logic Programming to people other than beginners is not encouraged.

Please  send email (to gupta@nmsu.edu  or  juris@nmsu.edu) if  you are 
interested in participating. Please indicate in your email if you just 
want to attend the session or  whether you  intend to  present a short 
position paper too.


---------------------------------------------------------------------
Gopal Gupta
Department of Computer Science	   email: gupta@nmsu.edu
Box 30001, Dept. 3CU		      	  gupta@compsci.bristol.ac.uk
New Mexico State University	   Ph: +1 (505) 646 6236 
Las Cruces, NM 88003-0001	   Fax: +1 (505) 646 6218
USA
---------------------------------------------------------------------
From: erik@pdnfido.fidonet.org (Erik VanRiper)
Newsgroups: comp.theory.cell-automata
Subject: Life for Unix
Date: 30 Aug 92 07:03:22 GMT
Followup-To: poster
Organization: The Source for Source Pub Access Unix

About a week ago I requested a source for source for LIFE.  I got a reply from
someone who said "email me, and I will send you a copy".  Well, I tried a 
return-reply so he could send it, but it bounced, had a HD failure, and lost
his/her address.  So, if that person would be so kind, YES, I would LOVE to 
have a copy of the source.

Thanx!

/* Erik */

-- 
Like wow...  This be a .sig, eh? 
GEEKS Anonymous - Join today!
The Source for Source - Pub Access Unix.  (516) 968-7824 or (516) 666-5877
Newsgroups: comp.theory.cell-automata
From: delusion@casbah.acns.nwu.edu (Albert Schmezer)
Subject: Programming Life in Tpascal
Organization: Northwestern University, Evanston Illinois.
Date: Mon, 24 Aug 1992 01:42:15 GMT

	Hello all! I am fairly new to Cellular Automata and EXTREMELY new to
this particular newsgroup. I would like to extend a hello to all.
	I am currently programming an adaptation of Conway's Life program in
TurboPascal V6.0 (although in a downward-compatible format to Tpascal V5.0)
and in the middle of testing out my program with the "spaceships" I have seen
posted here a short while ago, I noticed that I seem to have an unusual bug
somewhere in the program which I can't locate. the simple "gliders" work
perfectly fine, but the LWSS spaceship works great until the 15th generation
when a singular pixel gets misplaced and the entire structure collapses.
	If anyone who works with both Life and TurboPascal could help me with
this problem I would greatly appreciate it. I am on limited time as I am a
high school student entering Senior year....
	Thanx,
<<delusion
 
	
Newsgroups: comp.theory.cell-automata
From: bc770@cleveland.Freenet.Edu (George Burgyan)
Subject: Benchmarks wanted
Organization: Case Western Reserve University, Cleveland, Ohio, (USA)
Date: Mon, 31 Aug 92 05:40:22 GMT


XLife users:

I am writing a Life program and would like to know how fast it is compared to
XLife in order to compare and analyze the algorithms. However, I can't run
XLife, so I am requesting that those of you who can, do this for me:
XLife (or at least release 3.0) has a benchmark feature, where you put in a 
pattern and it asks you how many generations to play and when done tells you
how long it took.
Could you please have it play the pattern 'acorn' (it looks like this)
.x.....
...x...
xx..xxx (I believe)
for 10,000 generations, and mail me the results.
I need to know the exact time reported and on exactly what machine you ran it.
I need as many as possible.

Thanks in advance!

--
G.
Newsgroups: comp.theory.cell-automata
From: kaufman@eecs.nwu.edu (Michael L. Kaufman)
Subject: Where can I find old posts from this group?
Organization: EECS Department, Northwestern University
Date: Fri, 28 Aug 1992 13:15:25 GMT

Is this group archived anywhere? I just started reading it, and I would like 
to see what I missed. On a similar note, are there any ftp sites with 
interesting collections of CA stuff?

Thanks, Michael


-- 
Michael Kaufman | I've seen things you people wouldn't believe. Attack ships on
 kaufman        | fire off the shoulder of Orion. I watched C-beams glitter in
  @eecs.nwu.edu | the dark near the Tannhauser gate. All those moments will be
                | lost in time - like tears in rain. Time to die.     Roy Batty 
Newsgroups: comp.theory.cell-automata
From: mike@highlite.uucp (Mike Wiik)
Subject: Request to David I. Bell
Organization: Gotham Communications Research
Distribution: comp
Date: Sun, 23 Aug 1992 02:44:57 GMT

I do not know David's email address, hence I am posting this.
Sorry for the waste of net.bandwidth.

Your article, part 1 of Spaceships in Life, expired at my site
just as I was reading it. I would appreciate it you could email
a copy...

Thanks!
	-Mike
	mike@highlite.gotham.com

-- 
   | o==== . : ... :  :  .     |Mail Me Neat Stuff->POB 3703 Arlington VA 22203
 --@-- . o o o ... O -O- o o : |No disclaimers needed: I actually pay for this.
   |           ... :  :        |-----------------------------------------------
mEssAGE fRoM sPAcE ARt stUdiOs |Man:TheMissingLinkBetweenApes&HigherIntelligence
Newsgroups: comp.theory.cell-automata
From: sprave@gonzo.informatik.uni-dortmund.de (Joachim Sprave)
Newsgroups: comp.theory.cell-automata
Subject: Re: Lit. on Problabilistic CA
Date: 28 Aug 1992 08:20:24 GMT
Organization: CS Department, Dortmund University, Germany
Distribution: world
NNTP-Posting-Host: gonzo

Once more: Probabilistic :-)

         //////\\
        /        \
       _|  _   _ |_
      |.|-(.)-(.)+.|
       \|    J   |/
        \   ---  /
         \      /
          "####"
		Joachim
From: degroot@mksol.dseg.ti.com (doug degroot)
Newsgroups: comp.theory.cell-automata
Subject: wanted: CAM on a Mac
Keywords: CAM, simulation
Date: 1 Sep 92 18:01:41 GMT
Organization: Texas Instruments

Does anyone out there know of a CAM implementation for the Mac?

Doug DeGroot
degroot@dog.dseg.ti.com
From: tom@clipper.ingr.com (Tom Granvold)
Newsgroups: comp.theory.cell-automata
Subject: Re: Spaceships in Conway's Life (Part 2a)
Summary: Help, I need part one.
	 .
Keywords: life
Date: 28 Aug 92 16:40:16 GMT
Organization: Intergraph Advanced Processor Division - Palo Alto, CA


    I need part 1 of the Spaceships on Conway's Life articles.
Part 2a and 2b arrived, but due to running out of I-nodes on our
system, I never saw part 1.  I would appreciate it is someone could
email me part 1.

Thanks in advance,
Tom Granvold
 ------------------------------------------------------
Mail:    2400 Geng Rd., Palo Alto, Calif. 94303
UUCP:    tom@clipper.ingr.com
------------------------------------------------------
From: sprave@gonzo.informatik.uni-dortmund.de (Joachim Sprave)
Newsgroups: comp.theory.cell-automata
Subject: Lit. on Problabilistic CA
Date: 28 Aug 1992 08:17:39 GMT
Organization: CS Department, Dortmund University, Germany
Distribution: world
NNTP-Posting-Host: gonzo


Does anybody know about books, articles etc.
on Probabistic Cellular Automata ? Please tell me.

Thanks in advance


         //////\\
        /        \
       _|  _   _ |_
      |.|-(.)-(.)+.|
       \|    J   |/
        \   ---  /
         \      /
          "####"
		Joachim
From: bc770@cleveland.Freenet.Edu (George Burgyan)
Newsgroups: comp.theory.cell-automata
Subject: Re: Benchmarks wanted
Date: 2 Sep 1992 10:43:14 GMT
Organization: A poorly-installed InterNetNews site
Distribution: inet
NNTP-Posting-Host: slc4.ins.cwru.edu


I'm still looking for XLife benchmarks. However, when I made my original post,
I didn't realize that the benchmark command was undocumented.Appereantly, the
way to use it is (capital) 'B'. Remember, it's 10,000 generations of an acorn,
and I need as many as possible.

Thanks in advance.

--
G.
Newsgroups: comp.theory.cell-automata
From: Richard J. Gaylord <gaylord@ux1.cso.uiuc.edu>
Subject: Re: wanted: CAM on a Mac
X-Xxdate: Wed, 2 Sep 92 05:31:59 GMT
X-Useragent: Nuntius v1.1.1d9
Organization: University of Illinois
Date: Wed, 2 Sep 1992 10:30:51 GMT
X-Xxmessage-Id: <A6CA024F75019B13@mm-mac19.mse.uiuc.edu>

wanted: CAM on a Mac


i've look  for a Mac-CAM but there is none. 

automatrix which makes the PC-CAM has no intention as far as i know of
making one.

for CA software, there is also a lack of stuff for the mac.

i've asked about Ray's Terris simulation being implemented on  the mac
but they didn't even bother to respond to the question.

rudy's ca program is not going to be put out on a mac, as far as i know.

the best ca software you can get for the mac is the one by ken katsaros
(i forget the name of the program)

i'm pretty disappointed that the ca community doesn't want to write CA
programs (especially Terris) for the Mac since Mac's are a major computer
in educational institutes
From: erik@pdnfido.fidonet.org (Erik VanRiper)
Newsgroups: comp.theory.cell-automata
Subject: Life
Date: 25 Aug 92 19:49:29 GMT
Organization: The Source for Source Pub Access Unix

I am looking for any Unix version of Life that will work under SYS V.  I would
like to play with it for a while and see what I can come up with.  ftp is OK,
and it should be in C.  

Appreciate any and all replies, email would probably be best.

Thanks.


-- 
Like wow...  This be a .sig, eh? 
GEEKS Anonymous - Join today!
The Source for Source - Pub Access Unix.  (516) 968-7824 or (516) 666-5877
Organization: Robotics Institute, Carnegie Mellon, Pittsburgh, PA
Newsgroups: comp.theory.cell-automata
Date: Mon, 31 Aug 1992 20:20:17 -0400 
From: "Jon C. R. Bennett" <jb7m+@andrew.cmu.edu>
Subject: Re: Benchmarks wanted



bc770@cleveland.Freenet.Edu (George Burgyan) writes:
> XLife users:
> 
> I am writing a Life program and would like to know how fast it is compared to
> XLife in order to compare and analyze the algorithms. However, I can't run
> XLife,

how come?

> for 10,000 generations, and mail me the results.
>I need to know the exact time reported and on exactly what machine you ran it.

31 seconds on a DECstation 3100

jon
Newsgroups: comp.theory.cell-automata
From: hiebeler@Think.COM (Dave Hiebeler)
Subject: Where can I find old posts from this group?
Organization: The Internet
Distribution: inet
Date: Mon, 31 Aug 1992 01:55:49 GMT


  Yes, the CA newsgroup/mailing-list is archived on think.com
(131.239.2.1); the archives are available for anonymous FTP under the
"mail" directory.  Look for the files "ca.archive*".  The old archives
are compressed; the current one is not.

--
Dave Hiebeler                  | hiebeler@think.com
Thinking Machines Corporation  | (617) 234-4070
Newsgroups: comp.theory.cell-automata
From: chughes@maths.tcd.ie (Conrad Hughes)
Subject: Re: Using lookup tables for faster Life Game calculations
Keywords: 8086 real mode lookup table life game
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Date: Thu, 27 Aug 1992 10:21:24 GMT

pdh@netcom.com (Phil Howard ) writes:

>The original method I examined involved calculating 4 cells in parallel.
About two years ago I implemented standard-rules life in assembler
on the ARM (a British RISC machine) - doing 32 cells at a time in
parallel (the ARM is a 32 bit processor).  By constructing a binary
adder with bits 0, 1, 2 and 3 of the live-neighbours count held in
separate registers I reduced a 32-cell operation to 45 1-clock cycle
instructions, with a resulting 3000000 (three million) cells-per-
second performance out of an 8MHz machine (memory load/store and
screen DMA overheads account for the remainder of wasted CPU time).
This compares fairly well with that 33MHz 486' 1.1 million cells-
per-second..  If you like I could try translating my 2-year-old
assembler source into C; mail me please - I don't normally ready
this group.

Conrad
-- 
,--------------------. Suicide City, Paranoid State. Geddout! trip to, heave'n'
|chughes@maths.tcd.ie| ho, up, down, to'n'fro you have no word please leave us
+-=>Conrad  Hughes<=-+ here close our eyes to the octopus ride isn't it good to
`-------<SICK>-------' be lost in the wood isn't it bad so quiet there . . .
Newsgroups: comp.theory.cell-automata
From: alopez-o@neumann.uwaterloo.ca (Alex Lopez-Ortiz)
Subject: Re: A sorting Exercise
Organization: University of Waterloo
Date: Tue, 25 Aug 1992 20:40:55 GMT

In article <1992Aug25.184708.352@dartvax.dartmouth.edu>, scot@moosilauke.dartmouth.edu (Scot Drysdale) writes:
> The question about sorting a sequence on a closed loop with every crossing
> labeled is called Jordan Sorting (from the Jordan Curve theorem, I assume).
> It can be done in linear time.  See
> 
> K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, "Sorting
> Jordan Sequences in Linear Time," Proc. Symp. Computational Geometry,
> pp. 196-203 (1985).
> 
> It was to appear in Information and Control in 1986, but I don't have a
> reference.

Sorting Jordan Sequences in Linear Time Using Level-Linked Search Trees

Vol 68

1986 

Information and Control


-- 
Alex Lopez-Ortiz                              alopez-o@maytag.UWaterloo.ca
Deparment of Computer Science                       University of Waterloo
Waterloo, Ontario                                                   Canada
Newsgroups: comp.theory
From: thiemo@cs.tu-berlin.de (Thiemo Weiss)
Subject: Make-Facilities (Theories)
Organization: Technical University of Berlin, Germany
Distribution: comp
Date: Fri, 4 Sep 1992 13:03:18 GMT

I have to write a special MAKE-Facility for a new computer-language called
OPAL. Is there anybody who can tell me literature-references for some theories
or strategies to write such a program (questions: `What should I write in files',
`What is to read from disk', `How to parse the tree of dependencies', `Which
informations should I collect', ...).

Answers please to: thiemo@cs.tu-berlin.de

Thank You

	Thiemo Weiss
Newsgroups: comp.theory
From: raghu@norway.fishkill.ibm.com (Raghu Hudli)
Subject: Is this problem NP-complete?
Date: Tue, 25 Aug 92 18:50:50 GMT
Reply-To: raghu@vnet.ibm.com
Organization: IBM Corp., E. Fishkill, NY

The problem is given a weighted graph G = (V,E) with positive weights
for all edges in E, the weight of a vertex v_i in V is defined as the
sum of the weights of edges incident on v_i. Find a subset S of V, such
that |S| = K and the graph G' = ((V-S), E') has no vertex whose weight 
is greater than a constant T. E' is  E - edges incident on vertices in S.

I have heuristic solutions for the problem that seem to work well. I wanted
to make sure that I was not missing the optimum solution if the problem were
not NP-complete. 

Thanks in advance for your response.

Raghu Hudli
-----------------------------------------------------------------------
Raghu V. Hudli                       Tel:   (914) 892-4188
IBM Corporation                      Fax:   (914) 892-4316 
E. Fishkill, NY                      email: raghu@vnet.ibm.com
------------------------------------------------------------------------
Disclaimer: The opinions/views expressed here are mine and my employer
does not necessarily concur with me.
From: MT30@lafibm.lafayette.edu (T'seliso Mosiuoa)
Newsgroups: comp.theory
Subject: Recent Results in the theory of NP-Completeness
Date: 31 Aug 92 14:08:01 GMT
Organization: Lafayette College
Originator: news@lafcol

I am currently working on a thesis that will somehow involve
NP-Complete Graph problems.  I would be very grateful if someone
out there would provide me with a list of references for the
recent developments in the field.  David S. Johnson used to
run a column in the Journal Of Algorithms, I was able to follow
that up until 1988. I would be happy also if someone out there
knew David Johnson's email address.
Thank you very much.

Tseliso Mosiuoa
(Mosiuoat@lafvax.lafayette.edu)
(mt30@lafibm.lafayette.edu)
Newsgroups: comp.theory
From: parasite@athena.mit.edu (Vince)
Subject: graph-drawing algorithms needed
Followup-To: comp.theory
Summary: whiny graph question
Keywords: graph drawing algorithms
Organization: Massachusetts Institute of Technology
Date: Mon, 31 Aug 1992 17:32:21 GMT


Hello.

A friend of mine is looking for an algorithm which will
take the adjacency matrix of a graph in and draw or layout
the positions of the nodes such that no two edges intersect
in a 2-space rendition of it.  Now before you jump and say
"Hey, this is impossible for an arbitrary graph" let me add
that he will only be inputting graphs for which such a "picture"
exists.  I'm not sure how he knows it exists.  

Thaaaannnnnksss.

-V
From: pwp@moose.cs.indiana.edu (Paul Purdom)
Newsgroups: comp.theory
Subject: SAT
Date: 1 Sep 92 18:38:36 GMT
Organization: Computer Science, Indiana University

This year there has been considerable interest in a simple greedy algorithm
for finding a satisfying assignment of Boolean formulas in conjunctive
normal form (SAT). The algorithm starts with an initial assignment of values
to the variables. It then considers local changes to the assignment which
reduce the number of clauses that are not satisfied. Algorithms of this
nature have been published in
1. J. Gu, Efficient local search for very large-scale satisfiability problems,
SIGART Bulletin 3(1):8-12, Jan. 1992.
2. Kazuo Iwama, Hidetoshi Abeta, and Eiji Miyano, Random Generation of
Satisfiable and Unsatisfiable CNF Predicates, Algorithms, Software,
Architecture, Information Processing 92, pp 322-328.
3. Elias Koutsoupias and Christos H. Papadimitrious, On the greedy algorithm
for satisfiability, Information Processing Letters 43 (1992) pp 53-55.

Also this algorithm was mentioned this year or last on the net (I don't
remember who mentioned it). Although it has long been known that an algorithm
of this nature could be applied to the SAT problem, it appears that it was
just this year (or last) that people became aware that this was a promising
algorithm.

My question is: Does anyone know how it happened that a large number of
researchers decided this year that this was a promising algorithm? Were there
some earlier results on this algorithm, either published or unpublished, that
increased the level of interest in this algorithm. In a quick reading of the
above papers I did not see any indication of why the authors had chosen this
algorithm to study. If I remember the note on this net correct, it took the
view point that it was already common knowledge that this was a good
algorithm. If so, it was common knowledge that I had been unaware of.

I will appreciate any help that people can give on trackinng down the origin
of the recent interest in this algorithm.
From: tdk@spitws75.sbil.co.uk (Tim Kempster)
Newsgroups: comp.theory
Subject: Constructive proof of directed graph unconectivity
Keywords: CON NLOG NLOG-Complete
Date: 3 Sep 92 16:11:09 GMT
Reply-To: tdk@spitws75.sbil.co.uk
Organization: Salomon Brothers International Limited

I am trying to find an alogrithm with NLOG complexity for the 
problem defined below. 

UNCON
INSTANCE: A directed graph G=(V,A), two vertices u,v \in V
QUESTION: Is there no path from u to v in G ?


This is the complement of the problem CON which has the same instance
and asks, "Is there a path u to v ? ". This problem has an NLOG 
solution and is infact NLOG complete w.r.t LOG space reduction. 

Immerman and Szelepcsenyi have shown NLOG = CO-NLOG so combining these
results we see UNCON is indeed in NLOG.

Is there a direct constructive proof of this fact ?

That is is there a Turing Machine algorithm (non-deterministic 
log space) which can resolve this question. I was thinking along the lines
of transforming an instance of UNCON into CON by taking the complement 
of G or the complement of the transitive closure ? A bit vaugue I know.

The proof that CON is in NLOG gives the algorithm for a TM explicitly. 


Can anyone help ?

Tim Kempster
From: kirk@cs.pitt.edu (Kirk Pruhs)
Newsgroups: comp.theory
Subject: FOCS and World Series
Date: 31 Aug 92 14:20:04 GMT
Organization: Computer Science Dept., University of Pittsburgh


For those baseball fans who plan to attend FOCS in Pittsburgh:

If the Pirates win their division (it that seems they have at 
least a 50% chance of accomplishing this), and they win the NLCS
(probably less than a 50% chance of this) then games 6 and 7 of
the world series will be played in Pittsburgh over the weekend
of FOCS (assuming that the series goes this far).

Game 6 is scheduled for Saturday, Oct. 24 
Game 7 is scheduled for Sunday, Oct. 25

	The games will probably be in the evening, although
	I do not know this for a fact.

Reserved tickets are $45, and reserved general admission tickets
are $25. Tickets can be ordered by sending a check to:


Pittsburgh Pirates
PO Box 6759
Pittsburgh, PA 15212

Include an extra $5 dollars for postage and handling with each order.
They will send you the tickets by mail.  Of course tickets for unplayed
games will be refunded, sans the handling fee. Last year they
sold out all the world series games by mail.

This is all the info that I have.

Kirk Pruhs
kirk@cs.pitt.edu

P.S. This probably means that hotel rooms will be hard to get
at the last minute if the world series looks like it is going
to be in town. 


Newsgroups: comp.theory