HDTenEightyP/NetNews huggingface dataset:
From: stark@cs.sunysb.edu (Gene Stark)
Subject: Re: Synthesizing loop invariants -- unsolvable?
Organization: SUNY at Stony Brook Computer Science Dept.
Date: Fri, 6 Nov 1992 12:45:46 GMT

>I've been thrashing about with the problem of automatically generating
>loop invariants for the purposes of program verification.  Is the general
>case of automatically synthesizing a loop invariant for any given loop
>unsolvable?

The standard proof of (Cook) relative completeness for Hoare logics proceeds
by showing how, given a desired postcondition expressed as a formula in a
suitable first-order language, one can can construct a formula expressing
the weakest precondition that will guarantee the postcondition upon
termination.  Finding these weakest preconditions includes the problem of
finding loop invariants.  The proof actually constructs the formulas, so
the problem of synthesizing loop invariants is solvable.  However, the
formulas themselves are in no way guaranteed to be "simple" or "understandable"
as they involve a number-theoretic encoding of possible program executions.

For more information, a good reference is: "Mathematical Theory of Program
Correctness", by de Bakker.

							- Gene Stark
From: ian@ponder.csci.unt.edu (Ian Parberry)
Newsgroups: comp.theory
Subject: Re: Wanted: Contact to approach for technical reports from Stanford University
Summary: SIGACT News is good
Date: 5 Nov 92 21:31:36 GMT
Article-I.D.: mercury.1992Nov5.213136.14293
Organization: University of North Texas, Denton

In article <1992Nov5.104317.21365@cs.tu-berlin.de> baldamus@cs.tu-berlin.de (Michael Baldamus) writes:
>Does someone know a postal or, preferably, e-mail address which one
>can approach for technical reports from the Computer Science
>Department of Stanford University?

The answer to this question can be found in the Technical Reports
Column run by Mark Wiess in ACM SIGACT News (specifically, Vol 23, No. 2,
1992).  Mark's column is invaluable in that it lists new technical reports
AND gives an email contact for each department surveyed.
____
Ian Parberry (ian@ponder.csci.unt.edu)
Dept. of Computer Sciences, Univ. of North Texas
"Bureaucracy is expanding to meet the needs of an expanding bureaucracy"
Xref: sparky comp.theory:2405 sci.math:14910
From: br0w+@andrew.cmu.edu (Bruno W. Repetto)
Newsgroups: comp.theory,sci.math
Subject: Re: NP Completeness Question
Date: 13 Nov 92 04:18:51 GMT
Article-I.D.: andrew.sf0vZ=q00YUn8_95Ry
Organization: Doctoral student, Industrial Administration, Carnegie Mellon, Pittsburgh, PA

Excerpts from netnews.comp.theory: 13-Nov-92 Re: NP Completeness
Question by Nicholas R. Swart@phonon 
.
.
.
> Professor E.R. Swart of the Computer Science Department at the University
> of Guelph, has recently developed a polynomial-sized linear programing
                                      ^^^^^^^^^^^^^^^^ ^^^^^^
> formulation of the graph isomorphism problem and he has been able to show
> that with minor modifications, this same formulation can be used to solve
> the Hamilton tour, clique and other subgraph isomorphism problems.
>  
> This proves that P=NP and all NP-complete and all other NP problems thus
> have polynomial time algorithms.
>  
> So to answer your question, 1 and 2 are probably both polynomial.
>  
> Nicholas
> Dept. of Elec. and Comp. Engineering
> University of Waterloo
> Waterloo, Ontario
> CANADA
> N2L 3G1
.
.
.

The math programming model may be polynomial-sized, but it may still
be a very difficult _integer_ program, and thus not linear.  This does
not prove that P=NP.  It will, if it is also shown that the polyhedron
defined by the formulation constraints has only integer vertices.

As Prof. Panayotis asks in a different message, could you provide
the relevant reference for this?  Dr. Swart gave a proof that P=NP
in '86 ('87?) that unfortunately turned out to be faulty.  Are you
referring to this?

Bruno.  br0w+@andrew.cmu.edu
Newsgroups: comp.theory
From: mwj@rz.uni-jena.de (Johannes Waldmann)
Subject: ? newsgroup or mailing list on computational geometry ?
Organization: Friedrich-Schiller-University Jena, Germany
Date: Fri, 06 Nov 1992 17:26:55 GMT

hello net. see the subject. is there such a thing?
i'm especially interested in visibility graphs.

please email, thanx v/m, johannes.
Newsgroups: comp.theory
From: wtyler@adobe.com (William Tyler)
Subject: Re: Uniform noise in d-sphere
Organization: Adobe Systems Inc., Mountain View, CA
Date: Fri, 6 Nov 1992 18:10:10 GMT

In article <3655@news.cerf.net> jcbhrb@nic.cerf.net (Jacob Hirbawi) writes:

>A third method might be the following: use spherical coordinates and
>pick uniform random numbers for each of the coordinates with the appropriate
>ranges. In three dimensions this would be:
>
>   (1) radius  uniform over (0,d)
>   (2) angle1  uniform over (0,2 pi)
>   (3) angle2  uniform over (0,  pi)
>
>This seems to be *too* simple but since I can't think of any point within the
>sphere being more favored than any other point I would think that the 
>distribution is in fact uniform. 

This is definitely wrong. To choose just one point of attack, radii
smaller than d/2 are equally likely to be picked as radii greater than
d/2. But the volume inside radius d/2 is much less than the volume
outside that radius (depending on the dimension of the hypersphere),
so points outside d/2 are much less likely to be chosen. This same
sort of objection applies to the other coordinates.

Bill



-- 
Bill Tyler      wtyler@adobe.com
Xref: sparky comp.theory:2365 sci.logic:1954 comp.ai.philosophy:6685 comp.robotics:2274 comp.databases.theory:593
From: sahle@csgrad.cs.vt.edu (Eskinder Sahle)
Newsgroups: comp.theory,sci.logic,comp.ai.philosophy,comp.robotics,comp.databases.theory
Subject: Human Computers....
Date: 7 Nov 92 23:54:27 GMT
Followup-To: comp.theory
Organization: VPI&SU Computer Science Department, Blacksburg, VA

Hello all:

I need some help....  I'm looking for examples in fiction literature
of super sophisticated communicative computers a la HAL. That is,
computers that talk and communicate like humans.  I'm not so much 
interested in those instances where it's a robot that cannot be
distinguished from a human being as in computers sounding human without
being almost totally human-like....  .

Thanks in advance.
Ahmed 
Newsgroups: comp.theory
From:  jvr@or.math.lgu.spb.su (Joseph Romanovsky)
Subject: Re: Elimination ordering question
Reply-To: jvr@or.math.lgu.spb.su
Organization: University of St-Petersburg
Date: Sun, 8 Nov 1992 08:53:23 GMT

sjha+@cs.cmu.edu (Somesh Jha) writes:
>
>I need some  literature on the following problem. I already have a proof that
>it is NP-complete. Given a family of sets which are subsets of
>{x_1,x_2, ... ,x_n}. I define what it means to eliminate x_i.
>We union together all the sets which contain x_i, remove x_i from it,
>and replace all these sets by the new set. Now we get a new family of
>sets. The problem is to find the best elimination ordering.

   See: U.Bertele, F.Brioshi, Nonserial dynamic programming,
        Academic Press, N.-Y., 1972
   They used this procedure for sequential elimination of variables
   in optimization problems, and considered the secondary optimization
   problem of the best ordering of these eliminations.

     - Joseph Romanovsky
------------------------------------------------------------------------
 Joseph Romanovsky       e-mail  <jvr@or.math.lgu.spb.su>
 Professor of Operat.Res.        <jvr%or.math.lgu.spb.su@relay.eu.net>
 Univ. of St-Petersburg   fax:    +7 (812) 428-6649
 St.-Petersburg, Russia   phone:  +7 (812) 315-4374
------------------------------------------------------------------------
From: bret@tfd.COM (Bret Weinraub)
Newsgroups: comp.theory
Subject: 4x4 matrx
Keywords: determinant matrix
Date: 6 Nov 92 15:33:21 GMT
Organization: Twenty-First Designs, Wash, DC

Does anyone out there know the formula for
taking the derminant of a 4x4 matrix?

a b c d

e f g h

i j k l

m n o p

Thanks
From: diderich@di.epfl.ch (Claude G. Diderich)
Newsgroups: comp.theory
Subject: How to approximate the following NP-complete problem?
Keywords: NP, NP-complete, Ptas, Apx, Max SNP
Date: 11 Nov 92 08:52:04 GMT
Reply-To: diderich@di.epfl.ch (Claude G. Diderich)
Followup-To: diderich@di.epfl.ch (Claude G. Diderich)
Organization: Ecole Polytechnique Federale de Lausanne, Suisse

Dear reader,

I am studying the complexity of the following problem. I am especially
interested  in classifying this problem in any apporximation class
(like Ptas, Apx, Max SNP, etc...). Do you know of any references or
results on this subject? Any personal ideas are greatly appreciated!
Please e-mail and I will summarize.

Here is the problem:
	You have a set of p linear equations of the form
	a_{i,1} x_1 + ... + a_{i,v} x_v = b_i for i \in {1..p}.
	Find a subset of equations that are satisfiable, e.g. that
	have a solution (not necessarily unique) and that is maximal
	in its dimension.

The problem can be solved in polynomial time if the number of
variables v is constant. 

But no approximation results are known to me by this time.

Thanks all theory folk for reading this,

Claude G Diderich

---------------------------------------------------------------------------
Claude G. Diderich                            Internet: diderich@di.epfl.ch
30, Avenue S.Reymondin  --  CH-1009 Pully (VD)  --  Switzerland  --  Europe

``Imagination is more important than knowledge''            Albert Einstein
---------------------------------------------------------------------------
From: kosowsky@minerva.harvard.edu (Jeffrey J. Kosowsky)
Newsgroups: comp.theory
Subject: Re: Uniform noise in d-sphere
Date: 9 Nov 92 16:45:04 GMT
Article-I.D.: minerva.KOSOWSKY.92Nov9114504
Followup-To: comp.theory
Organization: Harvard Robotics Lab, Harvard University

In article <3655@news.cerf.net> jcbhrb@nic.cerf.net (Jacob Hirbawi) writes:
>   A third method might be the following: use spherical coordinates and
>   pick uniform random numbers for each of the coordinates with the appropriate
>   ranges. In three dimensions this would be:
>
>	 (1) radius  uniform over (0,d)
>	 (2) angle1  uniform over (0,2 pi)
>	 (3) angle2  uniform over (0,  pi)
>
>   This seems to be *too* simple but since I can't think of any point within the
>   sphere being more favored than any other point I would think that the 
>   distribution is in fact uniform. 
>

Not only is this *too* simple but it is also wrong. Picking radii and
angles uniformly does *not* give a uniform distribution with respect
to the standard (Euclidean) volume measure on the sphere. Remember the
Jacobian term in the change of variables formula. Just because a map
is one-to-one (eg: your spherical coordinate system is almost a
one-to-one covering of the sphere) does not mean that it preserves
measure!

Jeff Kosowsky
Newsgroups: comp.theory
From: dsims@don.ece.uc.edu (David Sims)
Subject: Synthesizing loop invariants -- unsolvable?
Organization: University of Cincinnati
Date: Thu, 5 Nov 1992 23:06:48 GMT

I've been thrashing about with the problem of automatically generating
loop invariants for the purposes of program verification.  Is the general
case of automatically synthesizing a loop invariant for any given loop
unsolvable?

I suspect it is but cannot come up with a proof.  Any help would be
appreciated.
-- 
David Sims              Dept. of Electrical and Computer Engineering
david.sims@uc.edu       University of Cincinnati
(513) 556-2499          Cincinnati OH  45221-0030
                        USA
Newsgroups: comp.theory
From: radha@bmerh249.bnr.ca (Radha Valiveti)
Subject: Call-for-papers for a Neural net conference
Organization: Bell-Northern Research, Ottawa, Canada
Date: Thu, 05 Nov 92 16:30:38 GMT

A little while ago, I noticed the call for papers for a neural net
conference taking place in Oregon, USA sometime in May/June 1993. As
far as I recall, the deadline for submission of papers was Jan 15,
1993.  I have accidentally deleted the message that I had saved. Could
someone please mail it to me?

thanks,
radha


--
___________________________________________________________________________
Radhakrishna S Valiveti              Bell Northern Research, Ottawa, Canada
Phone: (613) 765-2741     Fax: (613) 765-4777          e-mail: radha@bnr.ca
___________________________________________________________________________
From: flow@gayakum.kaist.ac.kr (Paek In-Hyeok)
Newsgroups: comp.theory
Subject: Random generation of simple polygons
Date: 9 Nov 92 12:37:07 GMT
Organization: TC lab. CS Dept. KAIST


Hi!
I'm looking for papers, source code, or refernces to random
generation of simple polygons.
If anyone could e-mail me, I would greatly appreciate.

				Thanks in advance,
				Paek Inhyeok

e-mail:   flow@gayakum.kaist.ac.kr or flow@jupiter.kaist.ac.kr
From: sjha+@cs.cmu.edu (Somesh Jha)
Newsgroups: comp.theory
Subject: Elimination ordering question.
Date: 5 Nov 92 17:48:25 GMT
Article-I.D.: cs.Bx984q.220.2
Organization: School of Computer Science, Carnegie Mellon



Hi:

I need some  literature on the following problem. I already have a proof that
it is NP-complete. Given a family of sets which are subsets of 
{x_1,x_2, ... ,x_n}. I define what it means to eliminate x_i. 
We union together all the sets which contain x_i, remove x_i from it,
and replace all these sets by the new set. Now we get a new family of
sets. The problem is to find the best elimination ordering. Or the
decision version will be to find an elimination ordering so that we
do not create a set of size greater that k during the elimination
procedure.

Any pointers? I know the problem is vague, but still I am hoping somebody
must have worked on a similar problem.

Thanks.
Newsgroups: comp.theory
From: ischuick@nusunix1.nus.sg (Hui Lucas Chi Kwong)
Subject: Request for implementation of suffix tree
Organization: National University of Singapore
X-Newsreader: TIN [version 1.1 PL6]
Date: Fri, 6 Nov 1992 09:33:13 GMT

Is there any public domain, or not expensive implementation of
the suffix tree data structure available?

I am thinking of writing
a string matching package where building of suffix tree is essential.

Any suggestions, pointers, and references are welcome. I will post
a summary afterwards. Please response by email to the address
"ischuick@nusunix1.nus.sg"

Thanks a million!!!

-- Lucas

-----------------------------------------------------------------------
Lucas Chi Kwong Hui,	    ischuick@nusunix1.nus.sg
Dept of Info Sys & Computer Science |	Blk 1E  Gillman Heights  10-46
National University of Singapore    |	Singapore 0410
Singapore 0511			    |
Tel : (+65) 7726733		    |	Tel : (+65) 2741544
Fax : (+65) 7794580		    |
-----------------------------------------------------------------------
From: henebry@matt.ksu.ksu.edu (Geoffrey M Henebry)
Newsgroups: comp.theory.dynamic-sys
Subject: books on quaternions?
Keywords: quaternions
Date: 11 Nov 92 04:45:01 GMT
Article-I.D.: matt.1drdadINNe6g
Distribution: inet
Organization: Kansas State University
NNTP-Posting-Host: matt.ksu.ksu.edu

greetings! does anyone have suggestions on books/articles that provide
readable but detailed discussions on quaternions & their applications? thanks!
+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ 
 Geoffrey M. Henebry                voice: (913) 532-7997   fax: (913) 532-6653 
 Division of Biology/Ackert Hall    internet:   gmh@andro.konza.ksu.edu         
 Kansas State University                        henebry@matt.ksu.ksu.edu        
 Manhattan, KS 66506 USA            Heraclitus: PANTA HREI                      
Newsgroups: comp.theory
From: krishna@cs.tamu.edu (Krishna Kumar)
Subject: Packages for solving sytems of polynomial inequalities.
Organization: Computer Science Department, Texas A&M University
Date: Fri, 13 Nov 1992 16:04:42 GMT


Does anyone know of good implementations of algorithms that
solve systems of polynomial inequalities ( integer coefficients with
solutions over the reals ). Programs based on cylindrical algebraic 
decomposition are fine, but if anyone has an implementation of
the algorithm by Grigoriev and Vrobjov I would be particularly interested.

krishna
 

Newsgroups: comp.theory
From: marcel@ADS.COM (Marcel Schoppers)
Subject: asymptotic value
Organization: Advanced Decision Systems, Mtn. View, CA (415)960-7300
Date: Thu, 12 Nov 1992 08:25:50 GMT

All,
	I need some help figuring out an asymptotically correct value.
Given the equation

		b^s = s + b^(s-2)

set b=1+c and find c in terms of s as s becomes large.  Empirically, c -> 0
from above, but how fast?  I can tell you that b^s >> s, but one has to be
very careful about using this fact.  For example, if you use it in the above
equation you get b=1 and immediately wipe out your chances of finding the
error term.  Rearranging the original equation one can get to

		b^s = s b^2 / (b^2 - 1)
		    : s/2c

where ":" means "approximately equal".

At this point if you substitute b=1+c on the left and expand, you get 1+sc
which is nowhere near right: at s = 900, b=1.01, c=.01, b^s=9000 and the
erstwhile approximation to 9000 is 1+sc=10.  So instead, raise both sides
to the power 1/s to get

By defn,	b = 1+c
From above,	  : (s/2c)^(1/s)
Taking logs,	c : (1/s) ln (s/2c)
		c*s : ln (s/2c)

Now at least we've got an equation in c and s only, but from here I'm stumped
how to get an asymptotic expression for c.  If we do

		c*s : ln s - ln 2c

we find that at s=900, the terms are all of comparable magnitude, so we can't
just drop one (they are, 9.0 : 6.8 - -3.9).  So now what?  Can anyone help?

Marcel

Newsgroups: comp.theory
From: cailm@cs.tamu.edu (Liming Cai)
Subject: Approximability of Dominating-Set
Organization: Computer Science Department, Texas A&M University
Date: Wed, 11 Nov 1992 22:29:43 GMT

Does Dominating-Set have bounded ratio approximation algorithm?  
I am interested in any recent progress on the approximability 
of Dominating-Set.   Thanks in advance for any pointer.

-- LC    

Xref: sparky comp.theory:2351 sci.math:14497
From: rgep@emu.pmms.cam.ac.uk (Richard Pinch)
Newsgroups: comp.theory,sci.math
Subject: Re: Uniform noise in a d-sphere
Keywords: Random vector in the hypersphere
Date: 6 Nov 92 10:30:34 GMT
Organization: Department of Pure Mathematics, University of Cambridge

In article <1992Nov5.211723.26238@bnlux1.bnl.gov> murphy@sscdaq.phy.bnl.gov (Michael Murphy) writes:
>
>I am trying to compute uniformly random noise inside a d-dimensional 
>sphere.  I have identified two ways of doing so:
>
[...]
>    
>(2) A faster, although perhaps wrong approach is:
>   1. Choose an arbitrary d-vector 
>   2. Normalize it so it is a point on the d-dimensional sphere
>   3. Multiply this normalized vector by a random number in [0,1]
>      raised to the 1/dth power.
>
>I believe that method two works.  However, when I project a large number of
>points in a high dimensional space (e.g. 25) onto the plane (by ignoring all
>but two coordinates), I get something that resembles a square.  My advisor
>is not so sure that this is correct and I can only give an intuitive
>argument as to why it may be true.

What do you mean by "an arbitrary d-vector"?  If you are choosing it
so that the components are, say, uniform on [-1,+1]; i.e. uniformly
in the hypercube, then you are not choosing the random direction
uniformly, i.e.  point on the curface of the hypersphere uniformly: 
there will be more vectors pointing towards a corner of the hypercube.

Try this.
Let V(r,d) be the volume of the d-dimensional hypersphere of radius r.

Procedure to pick a random vector (x_1,...x_d) in the d-dimensional 
hypersphere of radius r.
1.  Pick x_d in [-r,+r] by choosing an element from the distribution
    with density V(x,d-1)/V(r,d) dx at x.
2.  Recursively generate (x_1,...,x_d-1) in the (d-1)-dimensional 
    hypersphere of radius sqrt(r^2 - x^d^2).

Richard Pinch
From: mattb@ssc-vax (Matt Baney)
Newsgroups: comp.theory
Subject: Automated Software Analysis
Date: 10 Nov 92 19:16:19 GMT
Reply-To: mattb@ssc-vax.boeing.com (Matt Baney)
Organization: Boeing Aerospace & Electronics

I am posting this for a colleague who doesn't have access to the net??
Please email any information directly to Debbie, or to me and I will
forward it??

thanks 
matt
-------------------------------------------------------------

  SUBJECT: Automated Software Analysis
  KEYWORDS:  Software analysis, reverse engineering, re-engineering,
             re-use.
  E-MAIL:  rickend@net.a1.ca.boeing.com   
             (!! thats a1 (as in the steak-sauce), and not aI or al !!)

  Recently attended a discussion on automated software analysis 
  tools for transformation of existing software systems into 
  reusable components.   I am looking for information on any tools 
  that may be available to parce an existing segment of source code, 
  create functionality flows, data control, flows, and/or relationships 
  of the functions and data (if possibly the source code is object 
  related), etc.  The purpose of these tools is to perform reverse
  engineering on existing software systems where the documentation and
  any diagrams of the system is out-of-date, and possibly incorrect.  
  Then the segments may then be incorporated into an upgraded version, 
  or even new, software systems (re-use).

  --Thanks,
  --Debbie


-- 
|  Matt Baney         | Boeing Defense and Space Division    |
|  -----------------  |   Knowledge Systems Group            |
| "I can't tolerate   | UUCP:        ..!bcstec!ssc-vax!mattb |        
| intolerant people!" | Internet:   mattb@ssc-vax.boeing.com |
Xref: sparky comp.speech:235 comp.ai:4201 comp.human-factors:2578
From: kuhu@sbustd.rz.uni-sb.de (Kurt Huwig)
Newsgroups: comp.speech,comp.ai,comp.human-factors
Subject: Re: Looking for speach synthesizer
Date: 9 Nov 92 11:10:32 GMT
Followup-To: comp.speech
Organization: Studenten-Mail, Rechenzentrum Universitaet des Saarlandes

The Amiga is capable of speaking English sentences. It's got two progs to do#
this:
1.Speak-Device, speaks Phonemes
2.Translate-Device, translates English sentences into Phonemes.

I programmed a translator for German sentences into phonemes. It was very
easy, cause German is spoken as it is written (English not, see (hear 
to boot and a book)). The same should be possible for French sentences, cause
French is also spoken as it is spelled.

Send me a mail if you want the program (written in C). It should be possible to
use it with every phoneme-speaking-device, not esspecially the Amiga.

Kurt

kuhu@stud.uni-sb.de

Newsgroups: comp.speech
From: s880836@minyos.xx.rmit.oz.au (Adam Dean Sbrana)
Newsgroups: comp.speech
Subject: Testing/training standards
Date: 6 Nov 1992 07:20:42 GMT
Organization: RMIT Computer Centre
NNTP-Posting-Host: minyos.xx.rmit.oz.au
Keywords: Neural networks

I'm presently trying to establish a set of speakers (on database) for training
and testing a speech recognition neural network.    

I am aware of the DARPA TIMIT Acoustic Phonetic Continuous Speech Database and 
would appreciate knowing if there are any other databases that may be around.

P.S.  I'm only interested in continuous speech at this stage.

Thanks,
Adam Sbrana
RMIT
email m880836@chudich.co.rmit.oz.au

Newsgroups: comp.speech
From: wgardner@qom.qualcomm.com (Bill Gardner)
Subject: LPC-10 or 10e
Organization: Qualcomm, Inc., San Diego, CA
Date: Wed, 4 Nov 1992 16:45:19 GMT

Hi,

  I know about the TI Source code for LPC-10 in the FAQ, but
does anyone out there know of any public domain source code
(C preferably) for LPC-10 or LPC-10e that is easily compileable 
on a Sun, Sparc, or PC??

   Thanks,

   Bill

Newsgroups: comp.speech