HDTenEightyP/NetNews huggingface dataset:
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: comp.theory,comp.lang.functional
Subject: Pointers in the pure lambda calculus (was: Re: Beta like reduction rules for lambda calculus)
Date: 29 Sep 1992 13:52:15 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
Distribution: inet
NNTP-Posting-Host: 129.89.7.4

In article <1992Sep21.071825.27580@cse.iitb.ernet.in> oberoi@cse.iitb.ernet.in (Sundeep Oberoi) writes:
>If anyone knows of any work on "beta like" reduction rules
>for lambda calculus, I would really appreciate it if they
>could mail me some references or any other pointers.

Well, consider the following notation to represent "assignments" to array
components (or when thinking of r as a "reference" operator -- to pointers
references):

                         let r(x) <- y in E

Define it as follows:

                  (lambda r.E) ( lambda z. if (z==x) y r(z) )

Then the following:

                 let ref(a) <- 1 in
                    let b = a in
                       let ref(b) <- 0 in
                           ref(a)

encodes the imperative language segment:

                   *a = 1; b = a; *b = 0; return *a;


Observe its Beta reduction:

              let ref(a) <- 1 in
                 let b = a in
                    let ref(b) <- 0 in
                        ref(a)
=
             lambda ref.(
                let b = a in
                   (lambda ref. ref(a)) (lambda z. if (z==b) 0 ref(z))
             ) (lambda x. if (x==a) 1: ref(x))
->           let b = a in
                (lambda ref. ref(a))
                   (lambda z. if (z==b) 0 (lambda x. if (x==a) 1: ref(x))(z))
->           (lambda ref. ref(a))
                (lambda z. if (z==a) 0 (lambda x. if (x==a) 1: ref(x))(z))
->           (lambda z. if (z==a) 0 (lambda x. if (x==a) 1: ref(x)) (z)) (a)
->           if (a==a) 0 (lambda x. if (x==a) 1: ref(x))(a)
->           if (true) 0 (lambda x. if (x==a) 1: ref(x))(a)
->           0

That's right:  0, not 1.  The a and b "alias".  Therefore, aliasing and
pointers are purely functional concepts, NOT imperative.

If you axiomatically define the <- operation, you'd might get a Beta reduction
along these lines (reducing from inside out for illustration here):

              let ref(a) <- 1 in
                 let b = a in
                    let ref(b) <- 0 in
                        ref(a)

->            let ref(a) <- 1 in
                 let b = a in
                    if (a==b) 0 ref(a)

->            let ref(a) <- 1 in
                 if (a==a) 0 ref(a)

->            let ref(a) <- 1 in
                 if (true) 0 ref(a)

->            let ref(a) <- 1 in 0

->            0

In many ways, "ref" behaves like a symbol table, or an environment.
From: scc@doc.ic.ac.uk (Shing Chi Cheung)
Newsgroups: comp.theory
Subject: Help: Algorithm for Cyclic -> Acyclic Graph?
Date: 30 Sep 1992 16:15:39 GMT
Organization: Dept of Computing, Imperial College, England
Distribution: world
NNTP-Posting-Host: deutsch.doc.ic.ac.uk
Keywords: Graph Algorithm

Hi! I am a PhD student in Imperial College and I am looking for a fast
graph algorithm to solve the following graph problem.

Given a cyclic digraph with a special root node in the graph, reduce
the cyclic graph into an acyclic digraph by removing the MINIMUM number
of edges but all the nodes reachable by the root node in the cyclic
graph must also remain REACHABLE by the root node in the acyclic
graph.

E.g.
               -------X
               |      ^
               v      |
Cyclic Graph:  S ---> X ----> X 
                      ^       |
                      |       |
                      ---------
	where S is the root node and Xs are common nodes.

                      X
                      ^
                      |
Acyclic Graph: S ---> X ----> X 

Another E.g.
               ------>X
               |      |
               |      v
Cyclic Graph:  S ---> X ----> X 
                      ^       |
                      |       |
                      ---------
                               
               ------>X
               |      |
               |      v
Acyclic Graph: S ---> X ----> X 
                               
My present solution is:
1) Work out an acyclic graph from the cyclic graph using DFS.
2) Work out the topological order in the acyclic graph. 
3) For each node in the cyclic graph (using the topological order)
     Propagate a tag from the node in the cyclic graph and remove those
     edges which propagate the tag back to the node.

However, I am not sure whether the algorithm removes the minimum number
of edges and whether there is a better standard algorithm.

Please reply by email.

Thank you.

S.C. Cheung (scc@doc.ic.ac.uk)
-- 
	SC Cheung	(scc@doc.ic.ac.uk  071-589 5111 ext 5092)
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: Accepting sequences?
Date: Mon, 05 Oct 1992 17:36:36 GMT
Organization: Security APL, Inc.

In article <LOWRY.92Oct4133535@rotor.watson.ibm.com> lowry@watson.ibm.com (Andy Lowry) writes:
>In article <1992Oct02.165008.37497@Cookie.secapl.com> frank@Cookie.secapl.com (Frank Adams) writes:
> > In any event, programs which run indefinitely do not generally do
> > *a* computation; instead they act as servers, performing and
> > completing multiple computations.
>
>This is a fairly limiting view of long-lived programs.  It may be a
>fairly common view currently, partly due to the success to date of the
>client-server paradigm for distributed computing.  But I think this is
>a case of a partial solution (to the problem of developing distributed
>systems) turning around and redefining the problem by obscuring the
>parts of it that it doesn't address.  People will have a need for
>long-lived, largely autonomous programs that have varied, dynamic
>interactions with other programs.  Many of these programs will act as
>servers, but many will not.  Examples are easily had by considering
>programs that carry on long-term intractions with the physical
>environment, like online market analysis programs.  The state of such
>a program at any given point in time is determined by its entire
>history of interactions, not by some recently initiated client
>interaction.  It's intended to run "forever," but it cannot be
>characterized as "completing multiple computations."

Widen your definition of "client"; the interaction with the feed from the
market is as much a client interaction as the interaction with a person on a
workstation, from the point of view of the program.  Yes, the program has a
database, but this is not unusual.  And it had better keep sufficient state
information in the database that it can start up again from it, because we
can't expect computers that *never* go down anytime soon.

Admittedly, a program which spent all its time between interactions doing
computations would be a somewhat different animal; but I am not familiar
with any that actually do this.  The paradigm is: get input, compute
something, write to the database; get request for output, read database,
compute solution, output it.

Newsgroups: comp.theory
From: yan-dicky@CS.YALE.EDU (Dicky Yan)
Subject: Weighted Matching Algorithms and MIP on Chordayl Graphs.
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
Date: Mon, 5 Oct 1992 06:32:12 GMT

Hi, does anyone know which is the fastest known algorithms for 

1. The Weighted matching problem on general graphs? [with weights on edges].
   I have found a O(|E|^3) algorithm in one of my textbooks.


2. The maximum weighted independent set (stable set) problem on chordal graphs.

Please reply by e-mail. Thank you.

Dicky Yan.
From: ped@csc.liv.ac.uk (Paul Dunne)
Newsgroups: comp.theory
Subject: Re: Halting problem
Date: 5 Oct 92 15:17:27 GMT
Organization: Computer Science, Liverpool University
X-Newsreader: TIN [version 1.1 PL6]

Kenneth Tolman (tolman%asylum.cs.utah.edu@cs.utah.edu) wrote:
> 
>   Let us suppose we construct a Turing machine which will solve the halting
> problem.  It is special in that it recognizes its own coding sequence, and
> stops with a special output character when it sees its own sequence.  This
> Turing machine is not susceptible to the self reference paradox which
> normally kills it.  What is wrong with this?

In order for the modified machine, call it HALT say,
to circumvent the `self-reference paradox' it
would have to output the special symbol whenever it sees
a TM that accepts the same language as HALT. Clearly
if HALT exists then there are infinitely many such TMs (for
example any machine which loops n times (n=1,2,3...) before
simulating the action of HALT). It follows that for the
self-reference paradox to fail, HALT would have to
capable of recognising the language

   CODE = < M : M is a Turing machine (code) recognising
                the same language as HALT)

It follows easily from Rice's Theorem for Recursive Index Sets 
that CODE is non-recursive (the proof of Rice's Theorem does
not involve a reduction to the Halting Problem so this argument
is non-circular)
From: victor@watson.ibm.com (Victor Miller)
Newsgroups: comp.theory
Subject: Re: Complexity of a problem related to permutation groups?
Date: 2 Oct 92 21:44:31 GMT
Reply-To: victor@watson.ibm.com
Organization: IBM, T.J. Watson Research Center
Disclaimer: This posting represents the poster's views, not necessarily those of IBM

>>>>> On 2 Oct 92 19:38:29 GMT, sjha+@cs.cmu.edu (Somesh Jha) said:

Somesh> Hi Folks:

Somesh> What is the complexity of the following problem? Given a permutation
Somesh> group G (acting on a set of size n) and two 0-1 vectors x and y of
Somesh> length n, find if x = perm y where perm is permutation in the
Somesh> permutation group G. I have a strong intuition that the problem is
Somesh> NP-complete (I know it is NP), but I haven't been able to prove it.

Somesh, This problem certainly is NOT NP-complete.  As you pose it,
the problem depends on classifying the orbit structure of G.  As a
simple example, if G is all of S_n (the symmetric group on n letters),
then x = perm y iff the number of ones in x = the number of ones in y.
Somesh> Thanks a lot.

Somesh> Somesh Jha
--
		Victor S. Miller
		Bitnet: VICTOR at WATSON
		Internet: victor@watson.ibm.com
		IBM, TJ Watson Research Center
		"Great artists steal; lesser artists borrow" Igor Stravinsky
Newsgroups: comp.theory
From: lowry@watson.ibm.com (Andy Lowry)
Subject: Nonterminating computations (was: Re: Accepting sequences?)
Date: Tue, 29 Sep 1992 15:27:49 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<1992Sep28.224552.100936@Cookie.secapl.com>
Organization: IBM T.J. Watson Research Center

In article <1992Sep28.224552.100936@Cookie.secapl.com> frank@Cookie.secapl.com (Frank Adams) writes:
 > In reality, computations complete.  Nobody runs an application program on
 > their computer forever.

I think reality's changing on this one, and has been changing for
quite a while.  If my workstation didn't crash every so often, I
suppose I'd run my X server pretty much "forever."  I expect that in
the coming distributed computing era we'll be seeing more and more
applications that are never intended to be shut off.  And I'm not just
talking about stateless, autonomy-less servers, which might as well
terminate and get restarted for new client calls.  I'm talking about
things like home monitoring software, trading software, desktops, etc.
Things that model and interact with aspects their environments, and
never terminate because the environment never does.

So here's a question: What, if anything, can/should computer theorists
do to address the needs of this sort of system?  What is there to help
in understanding the behavior of these systems, not just in isolation,
but in a dynamic setting where the conglomeration of long-lived
systems exhibits behaviors that result more from their interactions
than from the behaviors of the individual interacting systems?  What
can be said about the problems of upgrading a long-lived system
without ever bringing it, or any other piece of the environment, down
for service?  Other relevant questions?
--
Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
Newsgroups: comp.theory,comp.client-server
From: klaus@hal.nta.no (Klaus Gaarder TFI)
Subject: Re: Accepting sequences?
Organization: Norwegian Telecom Research
Date: Fri, 2 Oct 92 09:39:30 GMT

In article <1992Sep28.224552.100936@Cookie.secapl.com>

frank@Cookie.secapl.com (Frank Adams) writes

>In reality, computations complete.  Nobody runs an application program on
>their computer forever.


Do not confuse 'computable function' with 'total function'!
Partial computable functions do not alway terminate
nevertheless they *are* termed computable. As to the application program:: this
depends strongly on your view of what an *application* is, some applications are
not meant to terminate, unless forcefully compelled to do so (e.g. X-windows
etc).

Klaus@NTR
-- 
    __o   
  _`\<,_  
 (*)/ (*) Claudio Caputti
+++++++++++++++++++++++++++++++++++++++^++++++++++++++++++++++++++++++++++++++
Free will - the result of chaotic amplification of quantum events in the brain.
------------------------------------------------------------------------------
Newsgroups: comp.theory
From: sbloch@silver.cs.umanitoba.ca (Stephen Bloch)
Subject: FOCS again
Summary: roommate wanted
Organization: Computer Science, University of Manitoba, Winnipeg, Canada
Date: Tue, 29 Sep 1992 17:10:08 GMT

Let's try this again, more precisely.  I would like a roommate for FOCS
for Sunday, Monday, and Tuesday nights.  If that matches your schedule
with Hamming distance <= 1, and if you want to save $40/night by sharing
a hotel room, please write me.  (I've gotten only one response so far,
with Hamming distance 2.)

					Steve Bloch
				sbloch@silver.cs.umanitoba.ca
-- 
					Stephen Bloch
				sbloch@silver.cs.umanitoba.ca
Newsgroups: comp.theory
From: jdcho@cad2.eecs.nwu.edu (Jun-Dong Cho)
Subject: Approximation bound on degree-constrained MST 
Organization: EECS Department, Northwestern University
Date: Mon, 5 Oct 1992 18:37:29 GMT

Is there anybody who is aware of the approximation bound on
degree-constrained MST?

Degree-constrained spanning tree problem is NP-complete.
INSTANCE: Graph G = (V,E), positive integer K \leq |V|.
QUESTION : Is there a spanning tree for G in which no vertex has degree
larger then K?
It remains NP-complete for any fixed K \geq 2.
For example, when k = 2, the problem is as hard as the 
wondering salesman problem (acyclic traveling salesman problem).
The approximation bound of wondering sales problem 
is 2 times length of the Minimum Spanning Tree.
What if k = 3 or 4, etc.? 

Jun-Dong Cho
Northwestern University
-- 
/  Gary (Kok-Hoo) Yeap		|   Email: yeap@eecs.nwu.edu  \
/  Department of EECS           |                             \
/  Northwestern University      |                             \
/  Evanston, IL 60208           |                             \
From: cholette@JSP.UMontreal.CA (Cholette Martin)
Newsgroups: comp.theory
Subject: ******************* FIND THE ERROR ! ************************
Date: 30 Sep 92 20:04:35 GMT
Organization: Universite de Montreal


 Just for the fun of it, I challenge anyone to find the error on page 129 of the

 book : Theory of Computation
   by : Derick Wood (University of Waterloo)
        Wiley publications

 Challenge your analytical skills.... I can assure you that there is indeed an error,

 who will be the first to find it ???


 Send me your answers, I will post the results!


 See you soon,
 Martin Cholette
 cholette@jsp.umontreal.ca
From: cet1@cus.cam.ac.uk (C.E. Thompson)
Newsgroups: comp.theory
Subject: Re: A Generalized Graceful Number
Date: 30 Sep 92 22:13:40 GMT
Organization: U of Cambridge, England

In article <9209241519.AA11392@hyowon.pusan.ac.kr>,
hgcho@HYOWON.PUSAN.AC.KR ("", Hwangue Cho) writes:
|>
|>       Do you know any references for this graph labeling problem ?
|>
|>       Problem : For a given graph, (especially complete graph),
|>       we label the vertices with distinct positive integers f(x)
|>       in { 1, 2, ..... } to have distinct edge (x,y) numbers, which
|>       is labeled  | f(x) - f(y) |. Find the labeling which
|>       minimizes  max { f(x) }
|> 
|>       Comment : This problem is a generalized graceful numbering.
|>
|>       If you let me know about this problem, I will deeply appreciate it.

Restricting to the case of the complete graph, then if the labelling had
been with f(x) + f(y) there are some known results (see [1], section C9 
for references). In particular if min (max {f(x)}) = N for the complete
graph on n vertices then N^{1/2}(1-epsilon) < n <= N^{1/2}+N^{1/4}+1. It
is hypothesized but unproved that n = N^{1/2}+O(1).

Something similar ought to be true for the | f(x) - f(y) | problem, but
a convincing argument to that effect escapes me at this time of night... 

In article <1992Sep28.095534.10526@olymp.informatik.uni-bonn.de>,
hermann@uran.informatik.uni-bonn.de (Hermann Stamm) writes:
|> 
|> A simple solution for complete graphs on n vertices is:
|> 
|>   define f(v_i):=2^(i-1) , 1<=i<=n
|> 
|> This is a generalized graceful numbering.
|> 
|> On the other hand this is a perhaps to pessimistic choice, since
|> I tried the following:
|> 
|>   f(v_1):=1
|>   for i:=2 to n do f(v_i):= "lowest allowed number"
|> 
|> which results in 
|> 
|>   1,2,4,8,13,21,31,....
|> 
|> The 78th number (the last I generated) was less than 7500, and this is
|> much less than 2^(80-1).
|> 
|> Thus more work needs to be done to close the gap between 2^(i-1) and the 
|> best value ...

Requiring the f(x) to be part of a common infinite sequence, as is 
certainly the case for this greedy algorithm, is known to make the
values non-optimal for some finite n in the f(x) + f(y) case. In
particular, lim sup f(x) / x^2 is infinite as x -> infinity.

[1] Richard K. Guy "Unsolved Problems in Number Theory"
    Springer-Verlag (1981) ISBN 0-387-90593-6

(Note the date: many of the results may have been improved by now.)

Chris Thompson
JANET:    cet1@uk.ac.cam.phx
Internet: cet1@phx.cam.ac.uk
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: Complexity question on DFA's
Date: Fri, 25 Sep 1992 14:30:41 GMT
Organization: Security APL, Inc.
Keywords: DFA, Automata, Union

In article <Bv4DBp.CG4@ux1.cso.uiuc.edu> sree@ux1.cso.uiuc.edu (sreenivas rama) writes:
>Hi:
>
>Given two minimal DFA's M_1 and M_2 on n_1 and n_2 states, what is the
>complexity of the best algorithm that computes another DFA M such that
>L(M) = L(M_1) \union L(M_2).  M need not be minimal but it should be a
>DFA. 
>
>The best that I can come up with is O(n_1 * n_2).  This is via
>DeMorganization over intersection. Is there something better than
>this?

Here's a hint: consider the languages (a^n_1)^* and (a^n_2)^*.
Newsgroups: comp.theory
From: jmount+@CS.CMU.EDU (John Mount)
Subject: Re: Complexity of a problem related to permutation groups?
Organization: Carnegie Mellon University
Date: Sat, 3 Oct 1992 17:11:20 GMT

In article <VICTOR.92Oct2174431@terse4.watson.ibm.com>, victor@watson.ibm.com (Victor Miller) writes:
> Somesh, This problem certainly is NOT NP-complete.  As you pose it,
> the problem depends on classifying the orbit structure of G.  As a
> simple example, if G is all of S_n (the symmetric group on n letters),
> then x = perm y iff the number of ones in x = the number of ones in y.

I don't see your point.  You show a particular subclass of the problem
is easy.  You might as well say that SAT restricted to two variables
per term is strong evidence that general SAT is not hard.

Unless you know that clasifying the orbit structure for all G (not
just S_n) is easy.

-- 
--- 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: bmb11@cus.cam.ac.uk (B.M. Bolker)
Newsgroups: comp.theory.dynamic-sys
Subject: dstool add-ons: not much luck but thanks anyway
Date: 29 Sep 92 10:37:32 GMT
Organization: U of Cambridge, England


   It occurred to me that I said I'd summarize.  Basically the 
answer is that no-one reading this group seems to have done
add-ons to dstool.  I got some kind replies from the people
working on dstool: 1) they're working on dstool (release 1.1
came out recently), but want it to be stable and reliable before
they let anything be released (hear hear), 2) kaos has slightly
more functionality.  Other people mentioned INSITE, xgobi (for
3-D stuff) from statlib, etc. ... I think most of the traffic
went through this group.
   Two more things:  I'm interested to know if anyone has done
any work in Mathematica with correlation dimension, Lyapunov
analysis etc. (and has codified their work into packages) ... I
haven't seen anything in the Mma archives I know about but
maybe I've missed something.  My impression is that Mma probably
doesn't have the guts for this kind of heavy numerical analysis
anyway but I'm curious.
   And someone asked me in e-mail if there's a FAQ list for this
group.  I haven't seen one, and I think there should be, but I'm
loath to volunteer to create it ... any volunteers?  (It could list
archive sites, perh. have a short bibliography, list known software
tools ... not that the traffic is so heavy, but the same questions
do seem to come up a lot.)

-- 
-----------------------------------------------------
Benjamin Bolker      Cambridge Univ. Dep't of Zoology
bmb11@cus.cam.ac.uk (Internet), bmb11@uk.ac.cam.cus (JANET)
From: steve@fulcrum.oz.au (Steve Taylor)
Subject: Re: FREE-ENERGY Technology
Organization: The Fulcrum Consulting Group
Distribution: inet
Date: Thu, 1 Oct 1992 01:49:08 GMT

In <9209280052.AA20549@nettlerash.berkeley.edu> MCELWRE@UWEC.BITNET ("NAME 'Robert E. McElwaine'") writes:


>                            FREE-ENERGY TECHNOLOGY
>                       by Robert E. McElwaine, Physicist

>               Fortunately, a few SMART people such as the Wright
>          Brothers did NOT accept such pronouncements as the final
>          word.  Now we take airplanes for granted, (except when they
>          crash).

These days, of course, we take loopy sounding free energy ideas for granted,
(except when they mysteriously never produce any working models).


>                                   Robert E. McElwaine
>                                   B.S., Physics, UW-EC


					Steve Taylor
					VeryImpressiveAcademicQualification