HDTenEightyP/NetNews huggingface dataset:
From: creutz@cco.caltech.edu (Michael John Creutz)
Newsgroups: comp.theory.cell-automata
Subject: a fun rule
Date: 4 Oct 1992 01:38:59 GMT
Organization: California Institute of Technology, Pasadena
Distribution: wo
NNTP-Posting-Host: alumni.caltech.edu


An amusing rule that generates some mind boggling graphics is
to consider either the eight or 4 cell neighborhood, have births
on all but zero live neighbors, survivors on all possibilities.
But before placing the new cell, first xor the result with the 
previous state of the cell (this is a well known way to produce 
reversible rules; just switch present and one step back).
Start with just a few scattered live cells and periodic boundaries
and you will see a few expanding walls.  Add a few more cells, and
when these walls get dense enough a rather psychedelic pattern evolves.

Mike

Newsgroups: comp.theory.cell-automata
From: tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman)
Subject: Looking for Stephen Wolfram... (refs)
Date: 3 Oct 92 18:58:01 MDT
Organization: University of Utah, CompSci Dept


  Hi, I am looking for work done by Stephen Wolfram.  I have a lot of
good stuff from before 86, but would like to look at more recent work
by him.  Anybody got a good lead off article?

  Also, any good recent articles on cellular automata in general would be
great!  Then I can research the whole area...

Thanks,


Newsgroups: comp.theory
From: bosch@cs.utwente.nl (Jan Bosch)
Subject: Kernighan-Lin like program (graph) partitioning
Keywords: partitioning (graph, program)
Organization: University of Twente, Dept. of Computer Science
Date: Mon, 5 Oct 1992 15:49:18 GMT

Dear theorists,

I am supposed to test our new heuristic algorithm against some others (heaviest
edge first, communication minima, etc) One of these algorithms is refered
to as 'Kernighan-Lin like partitioning'. I scanned the citation index, but
did not find anything useful. My question is (obvious):

	Could some please send me a reference to this algorithm?

or perhaps a (short) description of the algorithm. The first, but especially
the second, will be very much appreciated.

Thanx in advance.

Cheers,

Jan Bosch

-- 
Jan Bosch		| Spaarnestraat 73, 7523 VK, Enschede, Netherlands
bosch@cs.utwente.nl	| voice: +31-(0)53-354614
i------------------- We have to tri harder! - (athlon)--------------------i
Newsgroups: comp.theory
From: fischer-michael@cs.yale.edu (Michael Fischer)
Subject: Re: Halting problem
Reply-To: fischer-michael@cs.yale.edu (Michael Fischer)
Organization: Yale University Computer Science Dept., New Haven, CT 06520-2158
X-Newsreader: TIN [version 1.1az (for az) PL6]
Date: Mon, 5 Oct 1992 13:40:43 GMT

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?

Nothing!  The problem isn't with self reference, it's with the
supposition that your machine solves the halting problem.  (Look up
the recursion theorem in any good computability or recursive function
theory text for more information about self reference.)  By
hypothesis, your machine M_e has the following property:
    M_e(x) = 2 if x = e
    M_e(x) = 1 if M_x(x) halts and x <> e
    M_e(x) = 0 if M_x(x) does not halt and x <> e
Using M_e, I can construct a new machine M' which does the following:
    M'(x) = 0 if M_x(x) does not halt
    M'(x) runs forever if M_x(x) halts
(Note that M'(e) runs forever since M_e(e) halts.)  Now, let f be the
coding sequence of M'.  One gets the "self reference paradox" when
considering M'(f).  Hence, M' does not exist, so your machine M_e does
not exist, either.
--
==================================================
| Michael Fischer <fischer-michael@cs.yale.edu>  |
==================================================
Xref: sparky comp.theory:2065 sci.math:12319
From: torbenm@diku.dk (Torben AEgidius Mogensen)
Newsgroups: comp.theory,sci.math
Subject: Re: Complexity question on DFA's
Keywords: DFA, Automata, Union
Date: 28 Sep 92 13:00:07 GMT
Organization: Department of Computer Science, U of Copenhagen

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?

I can't see why you need DeMorganization over intersection.

The obvious way to construct a DFA for L(M_1) \union L(M_2) is to let
each state in the new automata be an element in (S_1 U {*})x(S_2 U
{*}), where S_i is the set of states in M_i. The idea is that there is
a transition from (p,q) to (p',q') on a symbol "a" if there is a
transition on "a" from p to p' im M_1 and from q to q' in M_2. The "*"
is used if one of the automata has no transition on "a":

	(p,q) -a> (p',q') iff p -a> p' and q -a> q'
	(p,q) -a> (*,q')  iff q -a> q' and no transition on "a" from p
	(p,q) -a> (p',*)  iff p -a> p' and no transition on "a" from q
	(*,q) -a> (*,q')  iff q -a> q'
	(p,*) -a> (p',*)  iff p -a> p'

The state (*,*) is not used. The initial state is (0,0) and a state
(p,q) is accepting if p or q is. (*,q) is accepting if q is, and (p,*)
is accepting if p is. Not all (p,q) may be reachable, so the number of
states will often be less than (n_1+1)*(n_2+1)-1.

This is also an O(n_1 * n_2) algorithm. A better worst case can not be
obtained, as you can find classes of languages L_i such that the
minimal DFA for L_i \union L_j (i<>j) has a number of states that is
the product of the number of states in the minimal DFAs for L_i and
L_j.

An example of this is L_i = the language consisting of n*p_i "a"'s,
where p_i is the ith prime number and n is an arbitrary integer. The
minimal DFA for L_i has p_i states. The minimal DFA for L_i \union L_j
has p_i*p_j states, where each state corresponds to the pair of
remainders with respect to division by p_i and p_j. This is exactly
the automata obtained by the construction above.

	Torben Mogensen (torbenm@diku.dk)
Newsgroups: comp.theory
From: pjyamamo@watdragon.uwaterloo.ca (Peter Yamamoto)
Subject: Re: ******************* FIND THE ERROR ! ************************
Organization: University of Waterloo
Date: Thu, 1 Oct 1992 21:49:09 GMT

In article <1992Sep30.200435.20497@cc.umontreal.ca> you write:
>
> 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 ???

Which error?

Errata: Theory of Computation
Derick Wood
Data Structuring group
Research Report CS-88-35
September, 1988

p. 129,l. 1, second sentence. It should begin ``Then, for...''
p. 129,l.3. Replace ``either $f$ ... conversely.'' by ``either $f$ and
$g$ are in $F$ or $f$ and $g$ are in $Q-F$.''
p. 129,l. 5. Replace ``...\delta(p,a)\over{i}{\equiv}\delta(p,a),...''
by ``...\delta(p,a)\over{i}{\equiv}\delta(q,a),...''

Peter
Newsgroups: comp.theory
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: Accepting sequences?
Date: Fri, 02 Oct 1992 16:50:08 GMT
Organization: Security APL, Inc.

In article <1992Oct2.093930.1372@nntp.nta.no> klaus@hal.nta.no (Klaus Gaarder TFI) writes:
>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.

It depends on exactly how you define things, but I've always seen
"computable function" used as a synonym for "total function".  A "partial
function" is not "computable"; it is only "partially 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).

That is exactly why I said "application program", not just "program".

In any event, programs which run indefinitely do not generally do *a*
computation; instead they act as servers, performing and completing multiple
computations.
Newsgroups: comp.theory
From: dak@messua.informatik.rwth-aachen.de (David Kastrup)
Subject: Re: Combinatorial Problem
Organization: Rechnerbetrieb Informatik  /  RWTH Aachen
Date:  7 Oct 92 01:14:37 GMT

wanka@uni-paderborn.de (Rolf Wanka) writes:

>Dear Theory Community:

>I think the following problem has been investigated (and solved)
>before it came to my desk.

>Given: An m-sided d-dimensional array consisting of N=m^d nodes,
>       numbered from (0,..,0) through (m-1,..,m-1).

>Task:  Compute the number X of nodes that have exact distance i from
>       the node numbered (0,..,0).

>This number X is very easy determined on the hypercube, for instance, and
>it is a nice exercise to compute X, if i<m.

>But it seems difficult to give a general formula (consisting of
>binomials, ...) for X.

First thing necessary to know would be your definition of distance.
Taxi? Euclidean? Reachable by i moves?
Newsgroups: comp.theory
From: mek@hydrox.enet.dec.com (Mark Klamerus)
Subject: graph planarization
Date: Tue, 6 Oct 92 06:22:49 PDT
X-Received: by usenet.pa.dec.com; id AA02262; Tue, 6 Oct 92 06:24:16 -0700
X-Received: by enet-gw.pa.dec.com; id AA04370; Tue, 6 Oct 92 06:20:05 -0700
X-Received: from hydrox.enet; by decwrl.enet; Tue, 6 Oct 92 06:22:49 PDT
X-To: comp.theory.usenet
X-Apparently-To: comp.theory.usenet


	Does anyone have any references for graph planarization?

	Specifically to layout graph nodes to minimize edge crossings.

	thanks,

	Mark Klamerus
	mek@hydrox.det.dec.com
Xref: sparky comp.theory:2056 comp.arch:9662
From: dlukas@kenmore.bu.edu (David Lukas)
Newsgroups: comp.theory,comp.theory.dynamic-sys,comp.theory.self-org-sys,comp.ai,comp.ai.neural-nets,comp.cog-eng
Subject: Boston University Cognitive and Neural Systems Colloquia
Date: 2 Oct 92 21:01:50 GMT
Followup-To: comp.theory
Distribution: ne
Organization: Information Technology, Boston University, Boston, MA, USA
Originator: dlukas@kenmore.bu.edu



                           Fall 1992 Colloquium Series

                           CENTER FOR ADAPTIVE SYSTEMS
                                       AND
                   DEPARTMENT OF COGNITIVE AND NEURAL SYSTEMS
                                BOSTON UNIVERSITY


October 6
IS THERE MOTOR PROGRAM GENERALIZATION: EXAMINING THE QUESTION AND ITS ANSWER
Professor Charles Wright, Department of Psychology, Columbia University

October 13
IMPLICIT MEMORY IN AMNESIA
Dr. Laird Cermak, Memory Disorders Research Center, 
Boston VA Hospital

October 20
VISUAL PATTERN RECOGNITION AND THE TEMPORAL LOBES
Professor Charles Gross, Department of Psychology, Princeton University

November 3
MOVEMENT NOTATION ANALYSIS REVEALS COLLECTIVE VARIABLES IN 
VERTEBRATE BEHAVIOR
Professor Ilan Golani, Department of Zoology, Tel Aviv University  

November 10
MAGNETIC RESONANCE IMAGING OF THE HUMAN BRAIN: FROM STRUCTURE TO FUNCTION
Professor David Kennedy, Professor of Neurology, Harvard Medical School, 
and Center for Morphometric Analysis, Massachusetts General Hospital

November 17
TOPOLOGY AND TOPOGRAPHY IN PRIMATE VISUAL CORTEX: TOWARDS
A UNIFIED COMPUTATIONAL MODEL OF FUNCTIONAL ARCHITECTURE
Professor Eric Schwartz, Department of Cognitive and Neural Systems, 
Boston University

November 24
THEORETICAL RESULTS IN MEMORY-BASED LEARNING
Professor George Cybenko, Thayer School of Engineering, Dartmouth College

December 1
GEOMETRY AND BIOPHYSICS: SOME CASE STUDIES
Professor Nancy Kopell, Department of Mathematics, Boston University

December 8
IMPLICIT MEMORY IN THE AUDITORY DOMAIN: COGNITIVE AND 
NEUROPSYCHOLOGICAL ANALYSES
Professor Daniel Schacter, Department of Psychology, Harvard University

                   All Talks on Tuesdays at 3:30 PM in Room 149
                        Refreshments at 3:00 PM in Room 241
                           111 Cummington Street, Boston
        
                                  PLEASE POST 

















Newsgroups: comp.theory
From: shayne@cs.swarthmore.edu (Ethan Shayne)
Subject: Gaussian randomization
Summary: more info on Gaussian randomization
Keywords: Gauss Gaussian randomization random
Organization: Swarthmore College
Date: Wed, 7 Oct 1992 01:54:06 GMT

Can anyone please tell me where I can get a simple explanation of the
Gaussian randomization algorithm? Preferably online somewhere, if possible?
Please email me any responses at eshayne@haverford.edu.
			Thanks,
				Ethan Shayne
				Haverford College
From: freeman@linc.cis.upenn.edu (Jon Freeman)
Newsgroups: comp.theory
Subject: IEEE TAI '93
Date: 29 Sep 92 20:31:02 GMT
Organization: University of Pennsylvania

Could someone please send me, or tell me where I can find, a copy of
the Call for Papers for IEEE Tools for AI '93?

				Thanks,
				 Jon
				 (freeman@gradient.cis.upenn.edu)

-------------------------------------------------------------------------------
All life is suffering.               |     Jon Freeman
The cause of suffering is desire.    |     University of Pennsylvania
I want my MTV.                       |     freeman@gradient.cis.upenn.edu
From: clong@remus.rutgers.edu (Chris Long)
Newsgroups: comp.theory,rec.puzzles,sci.math
Subject: The Last Word on Brown Eyes, Blue Eyes
Date: 26 Sep 92 12:07:59 GMT
Followup-To: comp.theory
Organization: Rutgers Univ., New Brunswick, N.J.

In article <1992Sep25.132133.7259@cc.gatech.edu>, Gil Neiger writes:

> To summarize the contribution of the visitor:  the visitor's statement
> is of a fact that everyone already knew.  However, by doing so, the
> visitor increases the knowledge of the population.  The increase in
> knowledge is with respect to what the people know about what the group
> knows.

You are absolutely wrong.  The original problem, as stated, is
inconsistent since the inhabitants are assumed to be logical
and the blue-eyed individuals have not deduced their status
yet (assuming the island has a sufficient history).  For a
better statement of this puzzle which avoids this problem see
the rec.puzzles FAQ.

The reason the original statement of the problem is flawed is
that it specified that the those who found out they had blue
eyes would immediately kill themselves, and this was in effect
previously.  In the rec.puzzles FAQ, no person takes any action
until a certain point (initiated by an outside element, a preacher
in this case).
-- 
Chris Long, 265 Old York Rd., Bridgewater, NJ  08807-2618
From: ian@ponder.csci.unt.edu (Ian Parberry)
Newsgroups: comp.theory
Subject: SIGACT News deadline approaching
Summary: deadline 1 month away
Date: 30 Sep 92 16:15:44 GMT
Article-I.D.: mercury.1992Sep30.161544.11880
Organization: University of North Texas, Denton

Reminder: the deadline for the next issue of SIGACT News is one month away.
SIGACT News is the quarterly newsletter of the ACM Special Interest Group
on Algorithms and Computation Theory.  The regular deadlines are:

	Fall issue,   1 November
	Winter issue, 1 February
	Spring issue, 1 May
	Summer issue, 1 August

I encourage everybody to use SIGACT News as a forum for issues important to
theoretical computer scientists.  As always, Letters to the Editor,
Transitions, Reports and Pictures from conferences, Articles,  Calls for
Participation, Conference Programs, and Announcements are welcome.
 
Electronic submissions are encouraged.  My email address is (either)
  ian@ponder.csci.unt.edu
  ian@hercule.csci.unt.edu
 
Send email or phone for information on submission procedures, or consult the
Submission Guidelines in issue number 1 of each volume, starting with Vol. 23,
No. 1, Winter 1992.  You can finger ian@ponder.csci.unt.edu to get my
regular mail and express mail addresses.
 
Your contributions and feedback are welcome.
----
Ian Parberry, ACM SIGACT News Editor
Dept. of Computer Sciences, Univ. of North Texas
(817) 565-2845 (desk and answering machine) 2767 (secretary) 2799 (fax)
Newsgroups: comp.theory
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: Accepting sequences?
Date: Mon, 28 Sep 1992 22:45:52 GMT
Organization: Security APL, Inc.

In article <1992Sep28.115938.15203@hellgate.utah.edu> tolman%asylum.cs.utah.edu@cs.utah.edu (Kenneth Tolman) writes:
>  What on earth does accepting sequences have to do with computability?
>In a standard CS text, the definition of a computation is a Turing machine
>that accepts a sequence, and then halts.  Here are a number of problems with
>it:
>
>1) It opposes what Turing himself defined.  Turing define numbers like pi, and
>e to be computable- all nonterminiating computations.  These are by definition
>noncomputable by the "new and improved" definition.

By this definition, and in a very real sense, pi is not computable.  You can
compute arbitrarily good approximations to pi, but not pi itself.

On the other hand, there is the notion of a "computable real number", which
is precisely a number to which arbitrarily good approximations can be
computed.

>2) The new definition has nothing to do with reality.  A real computation 
>on a universal Turing machine would read in a sequence and then COMPUTE
>something- possibly halting or not.

The definition as quoted above does not say what is computed.  In fact, the
result is the output on the tape when the computation finishes.

>So what is the deal?  Why this weird obscure definition which has nothing
>to do with reality?

In reality, computations complete.  Nobody runs an application program on
their computer forever.
Newsgroups: comp.theory
From: niall@nmsu.edu (Niall Graham)
Subject: Inverse of a finite transducer
Organization: Computing Research Lab
Distribution: comp
Date: Wed, 30 Sep 1992 07:34:51 GMT


A finite state machine (transducer) is invertable iff 
it is "lossless of finite order"  See Kohavi 2nd ed .p541.
Now for each such machine M, an inverse machine M' must exist,
such that upon connecting the output of M to the input of
M' a new machine M" is created that writes what it reads, possibly
after some delay.
Now if M happens to be *linear*, it is very simple to construct the
inverse M', as it merely requires the determination of the inverse
of a certain matrix associated with M. But when M is not linear 
the problem is more difficult.
Now an example is presented in Kohavi that generates the
inverse of a certain machine M. However, it is not
obvious to me how this example should be generalized.
(More specifically, I have an example where the inverse
is incompletely specified, although the difficulty is
easily fixed by some ad hoc modifications of the result)
My question is this: 
Does anyone know of any reference on the general problem of 
finding the inverse of a finite state machine?
It would probably date from the 60's.
Thanks in advance,
--

Niall Graham          "Punctuality is the thief of time"
Los Alamos                                   Oscar Wilde
From: grove@triangle.Berkeley.EDU (Eddie Grove)
Newsgroups: comp.theory
Subject: circuit for exclusive or
Date: 30 Sep 1992 19:43:40 GMT
Organization: University of California at Berkeley
Distribution: inet
NNTP-Posting-Host: triangle.berkeley.edu


I am interested in the smallest "delay" of a circuit for computing
parity of n inputs.

The circuit is to be made up of 
	fan-in 2  AND  gate with delay 1
        fan-in 2  OR   gate with delay 1
        fan-in 1  NOT  gate with delay 0

The delay of the circuit is the maximum over paths from
inputs to the output of the sum of the delays along the
path.  Of course no cycles are allowed.

The obvious solution is to compute the parity of the first
floor(n/2) inputs and XOR that with the parity of the last 
ceiling(n/2) inputs.  This gives delay 2 * ceiling (log_2 n).

Does there exist an n for which there is a circuit with delay
less than 2 * ceiling ( log_2 n)?  For example, a circuit on
17 inputs with delay less than 10 would be of interest to me.

Eddie Grove
From: jmount+@CS.CMU.EDU (John Mount)
Newsgroups: comp.theory
Subject: Re: Complexity of a problem related to permutation groups?
Date: 2 Oct 92 23:13:39 GMT
Article-I.D.: cs.BvIoIt.LIp.2
Organization: Carnegie Mellon University

In article <BvIEK6.9r8.2@cs.cmu.edu>, sjha+@cs.cmu.edu (Somesh Jha) writes:
|> Hi Folks:
|> 
|> What is the complexity of the following problem? Given a permutation
|> group G (acting on a set of size n) and two 0-1 vectors x and y of
|> length n, find if x = perm y where perm is permutation in the
|> permutation group G. I have a strong intuition that the problem is
|> NP-complete (I know it is NP), but I haven't been able to prove it.
|> 
|> Thanks a lot.
|> 
|> Somesh Jha

In 

Prasad Chalasani, Oren Etzioni and John Mount ``Integrating learning
\& problem solving algorithms in permutation environments'' in 
"Knowledge Representation" proceedings, April 1991 at Cambridge.

My coauthors and I were able to show (in an appendix since we felt this
must be a known result) that this is equivalent, with respect to randomized
poly time Turing reductions, to the Setwise Stabilizer Problem (itself at least
as hard as graph isomorphism but not known to be NP complete).  

The reference for Setwise Stabilizer is

Christoph M. Hoffmann.  "Group-Theoretic Algorithms and Graph
Isomorphism", Springer-Verlag, 1982.

Hope this helps.

-- 
--- 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
Newsgroups: comp.theory,uw.cs.theory
From: hhon@neumann.uwaterloo.ca (Henry Hon)
Subject: Text booke about computational complexity
Originator: hhon@neumann.uwaterloo.ca
Organization: University of Waterloo
Distribution: na
Date: Mon, 28 Sep 1992 07:10:06 GMT


Newsgroups: comp.theory