HDTenEightyP/NetNews huggingface dataset:
From: selman@allegra.att.com (Bart Selman)
Newsgroups: comp.theory
Subject: Re: SAT
Date: 4 Sep 92 19:46:55 GMT
Reply-To: selman@allegra.att.com
Organization: AT&T Bell Laboratories
In-reply-to: pwp@moose.cs.indiana.edu's message of 1 Sep 92 18:38:36 GMT

Following up on Purdom's question about satisfiability
algorithms, below are two other references that might be of
interest. The first paper describes how to generate
random formulas that are very hard for the Davis-Putnam
procedure, and the second paper describes how a local search
method substantially outperforms the Davis-Putnam procedure on such
formulas. (I briefly reported on this work on the net before.)

  Bart Selman
  AT&T Bell Laboratories

=====================================================
Hard and Easy Distributions of SAT Problems
   David Mitchell, Bart Selman, and Hector Levesque
   Proc. of the Tenth National Conference on Artificial Intelligence 
   (AAAI-92), San Jose, CA, July 1992, 459--465.

A New Method for Solving Hard Satisfiability Problems
   Bart Selman, Hector Levesque, and David Mitchell,
   Proc. of the Tenth National Conference on Artificial 
   Intelligence (AAAI-92), San Jose, CA, July 1992, 440--446.

Papers are available via anonymous ftp:
        ftp research.att.com
        login: anonymous
        password: [optional]
        cd dist/ai
        get hsat.ps.Z  % compressed postcript file
        get gsat.ps.Z  % 
   Let me (selman@research.att.com) know if you encounter any 
   problems in printing the postscript file(s).
Newsgroups: comp.theory
From: boehm@parc.xerox.com (Hans Boehm)
Subject: Re: Are there reductions from Hilbert's 10th problem?
Organization: Xerox PARC
Date:  2 Sep 92 17:43:59 GMT

A reasonably well-known reduction from Hilbert's 10th problem can
be found in:

Warren D. Goldfarb, ``The Undecidability of the second-order unification
problem'', TCS 13 (1981), pp. 225-230.

The result has been used to prove undecidability for some type inference
problems for typed programming languages.

(Attempts to reply be email failed.)

Hans-J. Boehm
(boehm@parc.xerox.com)

Newsgroups: comp.theory.self-org-sys
From: afshin@nynexst.com (Afshin Goodarzi)
Subject: Re: Self-org applied to info systems?
Reply-To: afshin@nynexst.com
Organization: Sun Microsystems, Inc.
Date: Tue, 8 Sep 92 15:17:08 GMT


>Has anyone done any research into dynamic information retrieval systems, and
>how one might be implemented (such as a dynamic hypertext system, with info
>constantly being added)?  Any help with ref's would be appreciated.

Please post the results back on the net or at least email me a copy if you have a 
compilation of ref.s on this topic....

many thanks.

afshin
afshin@nynexst.com
From: langston@memstvx1.memst.edu (Mark C. Langston)
Newsgroups: comp.theory.self-org-sys
Subject: Self-org applied to info systems?
Date: 6 Sep 92 23:16:41 -0600
Distribution: world
Organization: Memphis State University

Has anyone done any research into dynamic information retrieval systems, and
how one might be implemented (such as a dynamic hypertext system, with info
constantly being added)?  Any help with ref's would be appreciated.



-- 
+--------8<------Cut Here------8<------Cut Here------8<------Cut Here---------+
  Mark C. Langston   |  "Secrecy is the beginning of tyranny."                 
  Psychology Dept.   |  "Always listen to experts.  They'll tell you what can't
  Memphis State U.   |     be done, and why.  Then do it."                      
      "Pftph!"       |           -From the notebooks of Lazarus Long         
Newsgroups: comp.theory
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: cute problem regarding finite automata
Date: Wed, 09 Sep 1992 17:14:25 GMT
Organization: Security APL, Inc.

In article <40853@gremlin.nrtc.northrop.com> johnson@nrtc.northrop.com writes:
>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.
>
>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.

Yes.  Outline of the proof:

Each state of the new machine is a set of possible tuples; each tuple is an
initial state (of the machine M for L), a current state, and a flag
indicating whether end of string has been found.  The initial states are
<S,S,no> for each state S of M.  The accepting states are those containing a
tuple <S,T,no> where S is the initial state of M and T an accepting state,
or a tuple <S, S, yes> for any state S of M.  I will not spell out the
transformations, but they are straightforward.
Newsgroups: comp.theory
Subject: Taboo?
From: news@husc3.harvard.edu
Date: 7 Sep 92 03:46:22 GMT

Newsgroups: comp.theory
From: jjverkui@cs.ruu.nl (Hans Verkuil)
Subject: A Program for Visualizing Geometric Transformations
Date: Tue, 8 Sep 1992 13:30:41 GMT
Organization: Utrecht University, Dept. of Computer Science
Keywords: Idual, dualities, duality transformations, Silicon Graphics, homogeneous coordinates, double wedges


What is Idual?
==============

Computational Geometry looks at algorithms and problems that deal with
geometric objects such as points, lines, planes and spheres in any number
of dimensions.  Many of the techniques that have been developed within the
Computational Geometry can be applied to such diverse fields as databases,
computer graphics and robotics.

One of the techniques that is often used is the duality transformation.  In
a nutshell, this technique transforms points to lines and vice versa.
Therefore, an algorithm for a point problem can be transformed into a dual
algorithm for a line problem.  For example, the dual of the convex hull
algorithm is an algorithm for determining the intersection of halfplanes.
Thus, the duality transformation technique can give you twice as many
results for the price of one.

Unfortunately, duality transformations are quite difficult to visualize and
this may prevent the use of these transformations in favor of other
methods, possibly not as efficient as duality transformations.

I have developed a program, called Idual, for the Silicon Graphics
Workstations that tries to help with the visualization of dualities.
In essence, Idual is a paint program with several unusual features.  
One of these features is that it only recognizes points, lines and circles, 
another one is that the dual of each point, line and circle is displayed 
in a second window.

This program has been made available at anonymous ftp-site 
'ftp.cs.ruu.nl' in directory 'pub/SGI'. There are two archives, the first one
(idualbin1.0.tar.Z) contains the binary and a PostScript user manual and the
second one (idualsrc1.0.tar.Z) contains the C-sources for the program and the
LaTeX-sources for the user manual. These LaTeX-sources also contain additional
information on the design and implementation of the program which are not
included in the user manual. Note that I have placed this program under the
GNU General Public License.


Comments? Bug reports? Ideas? 
=============================

You can reach me by email at address 'jjverkui@praxis.cs.ruu.nl' for some time
yet, but my account can disappear at any time, so you are warned! My 'normal' 
mail address is:

			Hans Verkuil
			Toendra 115
			2904 TK  Capelle a/d IJssel
			The Netherlands


-- 

----------------------------------------------------------------------------
   Hans Verkuil, Toendra 115, 2904 TK  Capelle a/d IJssel, The Netherlands
 Student Computer Science - Utrecht University - (jjverkui@praxis.cs.ruu.nl)
From: nmm@cl.cam.ac.uk (Nick Maclaren)
Newsgroups: comp.theory
Subject: Re: Matrix Square Root
Date: 10 Sep 92 07:53:31 GMT
Reply-To: nmm@cl.cam.ac.uk (Nick Maclaren)
Organization: U of Cambridge Computer Lab, UK

In article <dak.716054795@kaa>, dak@kaa.informatik.rwth-aachen.de (David
Kastrup) writes:
> Kevin.D.Brunson.1@nd.edu (Kevin D. Brunson) writes:
> > ....
> >		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.  ....
  
> 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.

I hit this problem when writing the multivariate normal random number
generator for the NAG library, and there are three solutions:

    1) Gaussian elimination on the original matrix plus a fudge constant
on the diagonals (which I vaguely remember as being 5*maximum
element*epsilon).

    2) Cholesky decomposition ditto (but the fudge constant is larger,
possible 13*...).  This is the method that the NAG code uses.

    3) A = T'DT decomposition, as described above, and replace negative
elements of D by zero.

    The speed stakes are (2) > (1) > (3) and the accuracy stakes are
exactly the converse.  In all cases, the difference is a small constant
factor, so there is nothing much in it.  For the theory of (1) and (2),
see Wilkinson and Reinsch - I don't know much about (3).


Nick Maclaren
University of Cambridge Computer Laboratory,
New Museums Site, Pembroke Street,
Cambridge CB2 3QG, England.
Email:  nmm@cl.cam.ac.uk
Tel.:   +44 223 334761
Fax:    +44 223 334679
From: jmount+@CS.CMU.EDU (John Mount)
Newsgroups: comp.theory
Subject: Pi(n)
Keywords: Pi
Date: 8 Sep 92 20:34:27 GMT
Article-I.D.: cs.BuA15F.DpH.2
Followup-To: comp.theory
Organization: Carnegie Mellon University

Hi,

I was wondering if anybody knows of an algorithm for computing Pi(n),
the nth digit of the decimal expansion of Pi, in time log(n)^k for
some k.  This is just an intellectual curiosity as I don't think this
would be useful for computing many digits of Pi as there are very
efficient methods to compute Pi to high accuracy.

-- 
--- It is kind of strange being in CS theory, given computers really do exist.
John Mount: jmount+@cs.cmu.edu               (412)268-6247
School of Computer Science, Carnegie Mellon University, 
5000 Forbes Ave., Pittsburgh PA 15213-3891
From: e_splett@trofs.enet.dec.com (Evan Splett)
Subject: Re: Weakest prespecification?
Organisation: Digital Equipment of Canada - Ottawa
Organization: Digital Equipment Corp.
Date: Tue, 8 Sep 1992 15:48:28 GMT


In article <12746@ecs.soton.ac.uk>, dbc@ecs.soton.ac.uk (Bryan Carpenter) writes...
> 
>     Somewhere in the past few days I saw a paper that talked
>about ``weakest prespecifications'' (and possibly attributed them to

These are the references that I know of:

The Weakest Prespecification
C.A.R. Hoare  and J. He 
Fundamenta Informatica   1986  vol 9     

The Weakest Prespecification
C.A.R. Hoare
Information Processing Letters  1987 vol 24 no 2

------------------------------------------------------------------------------
         Evan Splett
Digital Equipment of Canada Ltd.
phone 819-772-7205  Fax 819-772-7226
  e_splett@kaofs.enet.dec.com
------------------------------------------------------------------------------
From: ola@duke.cs.duke.edu (Owen L. Astrachan)
Newsgroups: comp.theory
Subject: big-O, big-Theta
Keywords: asymptotic analysis
Date: 15 Sep 92 16:21:14 GMT
Organization: Duke University Computer Science Dept.; Durham, N.C.


Texts aimed at students in introductory courses most often use big-O
notation exclusively, no mention is made of Omega or Theta.  Often an
informal definition of big-O is given, one that emphasizes "throwing out
constants and ignoring all but the leading term in a polynomial
expression".

For example, in Hopcroft and Ullman's _Foundations of Computer Science_
there is a substantial section on big-O including using big-O to give
"tight big-O bounds".  In Cormen/Leiserson/Rivest 's _Algorithms_ we see

   " Many people continue to use the O-notation where the $\Theta$-notation
     is more technically precise."

I'm interested in whether there is a consensus as to the correct
approach.  The Advanced Placement Computer Science exam is revising it's
curricular guidelines and using something perceived as anachronistic is
not our most fervid desire.  We run into trouble when we have multiple
choice questions since we must do things like:


      < code or algorithm description >

which of the following is the best description of the runtime of the ___
above?

(A)  O(log n)
(B)  O(n)
(C)  O(n log n)
(D)  O(n^2)
(E)  O(n^2 log n)

Note that we can't say "which of the following is correct", because
picking the largest expression always works.  Using Theta could
alleviate some of these problems, but it would go against the practice
employed in most intro books aimed at programming courses but which
sometimes include informal asymptotic analysis.

----

Thanks for any help, opinions, advice.  I'd prefer email responses, I'll
summarize to this group if there's interest.

Owen

Owen L. Astrachan               internet: ola@cs.duke.edu
Dept.of Computer Science        Phone (919) 660-6522
Duke University                 fax (919) 660-6519
Durham NC 27706
From: eker@loria.crin.fr (Steven Eker)
Newsgroups: comp.theory
Subject: Re: graph-drawing algorithms needed
Keywords: graph drawing algorithms
Date: 4 Sep 92 17:54:14 GMT
Organization: CRIN (CNRS) Nancy - INRIA Lorraine

In article <1992Aug31.173221.6257@athena.mit.edu>, parasite@athena.mit.edu (Vince) writes:
|> 
|> 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

There is a discussion of just this problem & 43 refs in

J. van Leeuwen, "Graph Algorithms", Chapter 10 of Handbook of Theoretical
Computer Science Volume A: Algorithms & Complexity, Elsevier, 1990.

Steven
Newsgroups: comp.theory
From: nv@scs.carleton.ca (Natana Valiveti)
Subject: Implementations for TSP heuristics
Reply-To: nv@scs.carleton.ca
Organization: School of Computer Science, Carleton University, Ottawa, Canada
Date: Thu, 10 Sep 1992 19:51:50 GMT



I am interested in implementations of Heuristics for the Travelling 
Salesman Problem.   I am particularly looking for implementations in C or Pascal suitable for the Unix systems.  Any information is welcome. 

Thank you,
---
__________________________________________________________________________
Natana Valiveti                                 e-mail: nv@scs.carleton.ca
School of Computer Science, Carleton University, Ottawa, Canada,   K1S 5B6
--------------------------------------------------------------------------
From: dbc@ecs.soton.ac.uk (Bryan Carpenter)
Newsgroups: comp.theory
Subject: Weakest prespecification?
Date: 4 Sep 92 18:22:57 GMT


     Somewhere in the past few days I saw a paper that talked
about ``weakest prespecifications'' (and possibly attributed them to
Hoare?).  I meant to go back and find out what this was about, but now I
can't remember where I saw the paper.  Does anyone know where I can
look this up?

    (It was definitely ``prespecification'', by the way.  If it
turns out that it's the same as ``precondition'' I'll be a bit
disappointed---I got the impression it was something different).

Bryan Carpenter
From: stst@vuse.vanderbilt.edu (Stefan Strack)
Subject: Wire World circuits sought
Organization: Vanderbilt University School of Engineering, Nashville, TN, USA
Date: Mon, 7 Sep 1992 18:25:20 GMT



Hi all, 

I am looking for circuits for the cellular automaton Wire World ranging
from basic (gates, clocks) to complex designs (someone mentioned a serial
shift-adder in this group). If you have designed something you'd like to
share or can point me to a source for circuits, please email me. I will
collect circuits, convert them into a standard format and post them to this
group if there's interest.

Thanks, Stefan (stst@vuse.vanderbilt.edu)
Newsgroups: comp.theory.cell-automata
From: xrjdm@twinpeaks.gsfc.nasa.gov (Joseph D. McMahon)
Subject: Re: Thanks to David Bell; life spaceships.
Reply-To: xrjdm@calvin.gsfc.nasa.gov 
Organization: NASA/GSFC NCCS
Date: Wed, 9 Sep 1992 14:25:03 GMT

May I also say thanks. I've saved the articles in the *large* archive I'm 
keeping of the Life-related stuff, to be played with at a later date. :-)

-- 
Joe McMahon |     "Those crusty old stodgers wouldn't know an exciting idea 
P.O. Box 13 |        if it picked up a lowpass filter and four-poled them."
Lothian, MD 20711 --------------------------------------------------------------
xrjdm@twinpeaks.gsfc.nasa.gov
From: steppe@ccwf.cc.utexas.edu (Top Changwatchai)
Newsgroups: comp.theory.cell-automata
Subject: Request for FAQ list
Date: 8 Sep 92 15:37:28 GMT

Is there an FAQ list for this newsgroup?  If so, could someone please send it
to me?

I'm thinking of writing a parallel cellular automata program; does anybody
have information on this?  (It's just my luck that the first time I read this
newsgroup, someone (Conrad Hughes) posts a parallel version of Life!)

Thanks,

Top

-- 
steppe@ccwf.cc.utexas.edu
"Nostalgia isn't what it used to be."
Newsgroups: comp.theory.cell-automata
From: hiebeler@Think.COM (Dave Hiebeler)
Subject: FAQ Request
Organization: The Internet
Distribution: inet
Date: Mon, 14 Sep 1992 15:11:45 GMT


  No, there is no FAQ for the cellular automata mailing-list/newsgroup.

--
Dave Hiebeler                  | hiebeler@think.com
Thinking Machines Corporation  | (617) 234-4070
Organization: Carnegie Mellon, Pittsburgh, PA
Newsgroups: comp.theory.cell-automata
Date: Sat, 12 Sep 1992 01:12:29 -0400 
From: Tom Lord <lord+@andrew.cmu.edu>
Subject: Re: Crystals in Life



Have you discovered any non-periodic crystals?

-t
From: shirley@fdr.jsc.nasa.gov (Bill Shirley [CSC])
Newsgroups: comp.theory.cell-automata
Subject: Re: Thanks to David Bell; life spaceships.
Date: 9 Sep 1992 15:07:20 GMT
Organization: Software Technology Branch - NASA/JSC
Originator: shirley@fdr


Thanks David,
  I have hardcopies to read on the nightstand and softcopies to
access on my computer.

  Boy, now I *really* want a good Life on my NeXT.  maybe I'll have to
write my own.  (Or just use Xlife, I wonder how that'd work)

-Bill Shirley
-- 
Bill Shirley		|  ``Computer Science is not about computers any 
shirley@fdr.jsc.nasa.gov|	more than astronomy is about telescopes.''
From: leue@crd.ge.com (Bill Leue)
Newsgroups: comp.theory.cell-automata
Subject: Re: Thanks to David Bell; life spaceships.
Date: 9 Sep 92 12:26:30 GMT
Reply-To: leue@crd.ge.com
Organization: General Electric Research & Development

David Bell should take heart.  The silence he is hearing in the newsgroup
is not indifference - far from it.  Awe-struck silence, perhaps.  I think
his series is one of the best things to show up in this group in quite a
while.  I have also appreciated the thread on better Life algorithms.

There have been several requests for a FAQ list.  Any takers?  (No, I'm
not volunteering :-)

-Bill Leue
leue@crd.ge.com
Newsgroups: comp.theory.cell-automata
From: holmes@opal.idbsu.edu (Randall Holmes)
Subject: Re: Thanks to David Bell; life spaceships.
Organization: Boise State University Math Dept.
Date: Fri, 11 Sep 1992 15:57:42 GMT

In article <1992Sep11.030025.20559@mnemosyne.cs.du.edu> mwgordon@nyx.cs.du.edu (Mike Gordon) writes:
>I really must agree with all of you, Dave Bell did a GREAT job with those
>postings!  Although I haven't hads much chance to play with those patterns,
>I did read and enjoy all of part 2 (a & b).
> 
> 
>Also, Dave do you have part 1 available via FTP (or email maybe) ?  I 
>missed it, but loved 2 and am downloading part 3 now.  
>
>Also, is there a good Life package for MS-DOS PCs available via FTP somewhere?
>I only have CGA, and the current programs I'm using is a MAJOR pain to use.    
>Therefore, I don't use it as much as I'd like.
>
>Mike Gordon   N9LOI 99681084@uwwvax.uww.edu
>   
>

Could someone e-mail me the spaceship files?
-- 
The opinions expressed		|     --Sincerely,
above are not the "official"	|     M. Randall Holmes
opinions of any person		|     Math. Dept., Boise State Univ.
or institution.			|     holmes@opal.idbsu.edu
From: jwmills@moose.cs.indiana.edu (Jonathan Mills)
Newsgroups: comp.theory.cell-automata
Subject: Re: Crystals in Life
Date: 14 Sep 92 18:55:13 GMT
Organization: Indiana University, Bloomington

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.

I did a study of crystals in 1988.  I have an unpublished manuscript,
maybe I should send it in!  Most of the work was developing crystals
and related objects: strings, ropes, fuses, crystal eaters, etc.

I have thirty or forty crystals made from blinkers, ropes and other
patterns.  Some can be made into fuses that "burn," exploding other
crystals.  Detonation waves in crystals can be initiated by gliders.
Some crystals can tolerate defects, other crystals are composites
(I can't recall the terminology for this, sounds like tectite).  The
most interesting objects are crystal eaters that excrete stable
patterns, transforming a dense pattern to a sparser pattern.
The problem is to make the edge stable, which as I recall can be
done with a toroidal space.  But without the wrap the eaters tend
to leave junk that wrecks the crystal excreta.

>
>(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.

Sounds quite interesting.  I never got that far.
From: erik@pdnfido.fidonet.org (Erik VanRiper)
Newsgroups: comp.theory.cell-automata
Subject: Life source for Unix
Date: 12 Sep 92 01:42:27 GMT
Organization: The Source for Source Pub Access Unix

Hello lifers.  (reminds me of the Marine Corps).  :-)

I asked a few weeks ago about obtaining some source in C for a basic LIFE 
program so that I could play too.  However, I got back 0 responses.  If at all
possible, could some kind soul send me the source to a regular-joe-shoe LIFE
that will compile on my SCO 386 box?  No X, just plain curses.  

I appreciate it, thanks!

/* 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: mwgordon@nyx.cs.du.edu (Mike Gordon)
Subject: Re: Thanks to David Bell; life spaceships.
X-Disclaimer: Nyx is a public access Unix system run by the University
	of Denver for the Denver community.  The University has neither
	control over nor responsibility for the opinions of users.
Organization: Nyx, Public Access Unix at U. of Denver Math/CS dept.
Date: Fri, 11 Sep 92 03:00:25 GMT

I really must agree with all of you, Dave Bell did a GREAT job with those
postings!  Although I haven't hads much chance to play with those patterns,
I did read and enjoy all of part 2 (a & b).
 
 
Also, Dave do you have part 1 available via FTP (or email maybe) ?  I 
missed it, but loved 2 and am downloading part 3 now.  

Also, is there a good Life package for MS-DOS PCs available via FTP somewhere?
I only have CGA, and the current programs I'm using is a MAJOR pain to use.    
Therefore, I don't use it as much as I'd like.

Mike Gordon   N9LOI 99681084@uwwvax.uww.edu