HDTenEightyP/NetNews huggingface dataset:
From: wt@informatik.uni-kiel.dbp.de (Wolfgang Thomas)
Newsgroups: comp.theory
Subject: Two Professor Positions Open at University of Kiel
Date: 21 Aug 92 23:05:24 GMT
Reply-To: Theory-A - TheoryNet World-Wide Events <THEORY-A%NDSUVM1.BITNET@cmsa.Berkeley.EDU>,
        Wolfgang Thomas <wt@informatik.uni-kiel.dbp.de>

TWO PROFESSOR POSITIONS AT THE UNIVERSITY OF KIEL (Germany)

(Translation of a Call for Applications from "DIE ZEIT" Nr. 34, 14.8.92,
p.35)

At Christian-Albrechts-Universitaet Kiel (Germany), and in the process of
establishing a "Technische Fakultaet" (Technical School with the disciplines
Electrical Engineering, Computer Science, and Material Science), the
following new professor positions are open in the Institute of Informatics
(Computer Science) and Practical Mathematics:

(1)  PROFESSOR (C3) OF COMPUTER SCIENCE
This professor position should represent the field "THEORY OF PARALLELISM".
The applicant should be qualified by research in areas such as:
Parallel/distributed algorithms, complexity of parallel computation, theory
of parallel processes, VLSI-theory.

(2)  PROFESSOR (C3) OF COMPUTER SCIENCE
This professor position should represent the field "COMPUTER-AIDED PROGRAM
DEVELOPMENT".
The applicant should be qualified by research in areas such as: Methods of
correct program development, automatic generation of programs from formal
specifications, program and process calculi and their implementation,
computer-aided software-engineering (CASE) and its foundation. Application
oriented cooperation for example with a planned CASE-center is desired.

For both professor positions, participation in courses of the basic and
advanced studies is expected (e.g. for the curricula "Diplom-Informatiker/in"
and "Diplom-Ingenieur/in" in computer science), as well as interest in
interdisciplinary cooperation with other research groups especially in the
Technical Faculty and the Faculty of Science.
Habilitation or equivalent scientific performance, e.g. in industrial
research, is required.
The university takes efforts in increasing the proportion of female
researchers. It therefore encourages qualified women to apply.
Disabled applicants will be considered with preference, provided
corresponding qualification is given.

Knowledge of German language is expected.

Applications with curriculum vitae, list of publications, scientific
background, and information on teaching experience viz. work in industry
should be directed UNTIL 21 SEPTEMBER 1992 to

Dekan der Technischen Fakultaet
der Christian-Albrechts-Universitaet zu Kiel
Olshausenstr. 40
W-2300 Kiel 1
Germany.
From: peschko@orca.micro.umn.edu (Edward Peschko)
Newsgroups: comp.theory
Subject: heuristic for solving large TSPs
Date: 18 Aug 92 14:46:57 GMT
Organization: University of Minnesota, Minneapolis: Under Grad Workstation Lab.

Greetings ---

I was wondering if anybody out there had the coding for a heuristic-based 
approximate solution to large (1000 cities or larger) TSP handy that I could
borrow, or a FTP site that contains the code/binary? (I am coding my own 
approach, and wanted some standards to test against....

Thanks in advance,

Ed Peschko
peschko@mermaid.micro.umn.edu---
Newsgroups: comp.theory.cell-automata
From: hiebeler@Think.COM (Dave Hiebeler)
Newsgroups: comp.theory.cell-automata
Subject: Book: The Global Dynamics of CA
Date: 14 Aug 92 12:16:59 GMT
Distribution: inet
Organization: The Internet


  I've been told that the following book is now available through
Addison-Wesley's SFI series.  You may have seen Andy's talk on this
subject if you were at the ALife-III conference.



THE GLOBAL DYNAMICS OF CELLULAR AUTOMATA
An Atlas of Basin of Attraction Fields of
One-Dimensional Cellular Automata.

Andrew Wuensche
Mike Lesser

Foreword by Chris Langton

Diskette included for PC-compatible computers.

Santa Fe Institute Studies in the Sciences of Complexity
Reference Vol 1 
Addison-Wesley Publishing Co. Reading MA, phone:(800) 447 2226
IBSN 0-201-55740-1   price: about $54

Abstract:
The Global Dynamics of Cellular Automata introduces a new global
perspective for the study of discrete dynamical systems, analogous to
the phase portrait in continuous dynamical systems.
   As well as looking at the unique trajectory of the systems future, 
an algorithm is presented that directly computes the multiple merging
trajectories that may have constituted the system's past. A given set
of cellular automata parameters will, in a sense, crystallize state
space into a set of basins of attraction that will typically have the
topology of branching trees rooted on attractor cycles. The explicit
portraits of these mathematical objects are made accessible. The Atlas
presents two complete classes of such objects: for the 3-neighbour
rules (elementary rules) and for the 5-neighbour totalistic rules. 
   The book looks in detail at CA architecture and rule systems, and
the corresponding global dynamics. It is shown that the evolution of CA
with periodic boundary conditions is bound by general principles
relating to symmetries of the circular array. The rule numbering system
and equivalence classes are reviewed. Symmetry categories, rule
clusters, limited pre-image rules, and the reverse algorithm are
introduced. The Z parameter (depending only on the rule table) is
introduced, reflecting the degree of pre-imaging, or the convergence of
dynamical flow in state space evident in the basin of attraction
field. A relationship between the Z parameter, basin field topology, 
and rule behaviour classes is proposed. A genotype-phenotype analogy
looks at the effect of mutating the rule table to produce mutant basin
fields.
   The accompanying software is an interactive research tool capable of
generating basins of attraction for any of the 2^32 CA rules in
5-neighbour rule space (for a range of array size), as well as
pre-images, space-time patterns and mutation. The operating
instructions are contained in the book.
                          * * * * * *

--
Dave Hiebeler                  | hiebeler@think.com
Thinking Machines Corporation  | (617) 234-4070
Newsgroups: comp.theory.cell-automata
From: 70302.3106@CompuServe.COM (Laurence F Wood)
Subject: Wire World References
Organization: The Internet
Distribution: inet
Date: Thu, 20 Aug 1992 11:52:32 GMT

Could anyone suggest some references on wire world?  If there are any
CAMEX or CAMPC programs out there that would also be interesting.  Who is
actively pursuing autamatons based upon wire world?

Thanks in advance.

Larry Wood

Newsgroups: comp.theory.cell-automata
From: rudy@autodesk.COM (Rudy Rucker)
Subject: Go Bugs
Organization: The Internet
Distribution: inet
Date: Sun, 16 Aug 1992 19:29:44 GMT


Antti Karttunen sends

 I recently downloaded Core Wars like game from Japanese ftp-site
called 'Jintori', which seems to be somewhat influenced by Go. It has
two bugs competing in two-dimensional space (instead of the traditional
one-dimensional Core Wars space), and the winner bug is the one which have
conquered more area in the end (by surrounding it). I wonder if this could
be made still more Go-like so that bugs' existence could be determined by
their liberties, count of eyes, and so on. In the end we maybe could
have the Go-playing program where the stones 'themselves' decide how to
play. Or even 'artificial life' system (See for example the July 1992
Scientific American article about the Genetic Algorithms) where the better
and better Go-playing algorithms would evolve. 

What an interesting idea!  A couple of  years ago I started simiulated
2D Turing machine programming.  The first ones I did were "Langton
vants" which I ran in a CA.  Then I started doing free-ranging 
linked list vants with many states which were available as a
shareware program called ant21.  These guys have lookup tables which
are bred with genetic algorithms.  The fitness functions I've used
at present have been based on splitting the bugs up into colonies,
and having them leave evanescent trails; the bugs get points by
running across a prey colony's trails and lose points be encountering
pred colony trails.  But Karttunen's rap suggests I might also keep
track of whenever a given bug's trail encloses a region and add this
region's pixel area to the bug's score.  What it is to properly "enclose"
a region is defined by the rules of Go.  The difference between Go Bugs
and a proper Go player is that each Go Bug plays its next stone within
some (preset but preadjustable) radius.  Real Go Players often keep
things happening at quite a few board location, they maintain multiple
Go Bugs.  Well, th en a Go Player could be a colony of Go Bugs.

A 2D Turing machine is like a CA cell that has come untethered.  It
reads its neighbor cells and changes its state.  But it also can
move, though when it moves, it paints the "aether" under it so that
its computation-record remains.
Newsgroups: comp.theory.cell-automata
From: ACW@RIVERSIDE.SCRC.Symbolics.COM (Allan C. Wechsler)
Subject: Birth only from antipodal parents
Organization: The Internet
Distribution: inet
Date: Mon, 17 Aug 1992 17:13:00 GMT

Mr. Howard expresses interest in a (binary, Moore-neighborhood) rule
where birth occurs when there are exactly two live neighbors, in
antipodal positions.  (A rule for survival is also given, but is not
relevant to my initial point.)

Such a birth-rule is unlikely to generate interesting behavior, because
the bounding octagon cannot grow.  If the configurations we want to
study have finite support, then there are no moving oscillators
(spaceships) and no patterns that grow without limit.  Therefore (in the
domain of finite patterns) the automaton can't be universal.

The rule Mr. Howard proposes has a fairly rich survival environment (115
environments out of 256 lead to survival) but an extremely poor birth
environment (4 out of 256).  My intuition is that almost all initial
configurations will stabilize very rapidly, leaving a fixed framework
that is consistent with the survival environment, punctuated with a few
"spark gaps" of approximately this form:

o...o
ooxoo
o...o

in which the cell marked "x" flashes.  Any more complex dynamics would
surprise me.

Has Mr. Howard actually tried this rule, say on a 50x50 toroidal board
seeded with random bits?
Newsgroups: comp.theory.cell-automata
From: bc770@cleveland.Freenet.Edu (George Burgyan)
Subject: Life algorithms
Organization: Case Western Reserve University, Cleveland, Ohio, (USA)
Date: Fri, 14 Aug 92 05:20:23 GMT


I am currently in the process of trying to write a Life program
for the PC.  I would like any and all suggestions for possible
algorithms and methods for computing next generation,displaying,
storing, etc...

In particular, I would like to know more about the algorithm
used in Xlife.  It seems rather intriguing, but as such is
poorly documented and I don't really have access to any sort of
X-term to run it.

Any help would be appreciated.

Thanks in advance!

-G.
From: paulh@minster.york.ac.uk
Newsgroups: comp.theory
Subject: Re: Multiple-Way Graph Partitioning refs?
Date: 20 Aug 92 08:18:30 GMT
Organization: Department of Computer Science, University of York, England
X-Newsreader: Tin 1.1 PL5

Here are some references that I picked up a while ago.
I hope they are helpful.

%T Cutting and Partitioning a Graph After a Fixed Pattern
%A Yannakakis, M.
%A P. C. Kanellakis
%A S. C. Cosmadakis
%A C. H. Papdimitriou
%P 712-722
%B 10th International Colloquium on Automata, Languages and Programming
%E J. Diaz
%D July, 1983
%C Barcelona, Spain
%J Lecture Notes in Computer Science
%V 154
%I Springer-Verlag
%K ICALP

%T The NP-completeness of some edge-partition problems 
%A Holyer, I. 
%X Shows that for each fixed n>or=3 it is NP-complete to determine whether an arbitrary graph can be edge-partitioned into subgraphs isomorphic to the complete graph K/sub n/. The NP-completeness of a number of other edge-partition problems follows immediately 
%K graph theory, computational complexity, NP-completeness, edge-partition problems, graph 
%O SIAM J. Comput. (USA) %J SIAM Journal on Computing
%V 10 
%N 4 
%P 713-17 
%D Nov. 1981

%T Efficient algorithm for graph-partitioning problem using a problem
transformation method
%A Lee, C.-H.
%A Park, C.-I.
%A Kim, M.
%X Shows that the uniform k-way partitioning problem can be transformed into
the max-cut problem using a graph modification technique. An iterative
algorithm, based on the Kernighan-Lin method, for partitioning graphs is
presented that exploits the problem equivalence property. The algorithm deals
with nodes of various sizes without any performance degradation. The computing
time per pass of the algorithm is O(kN/sup 2/), where N is the number of nodes
in the given graph. In practice, only a small number of passes are typically
needed, leading to a fast approximation algorithm for k-way partitioning.
Experimental results show that the proposed algorithm outperforms the KL
algorithm in the quality of solutions
%K graph-partitioning problem, problem transformation method, uniform k-way
partitioning problem, max-cut problem, graph modification technique, iterative
algorithm, Kernighan-Lin method, problem equivalence property, nodes, computing
time, passes, approximation algorithm
%J Computer Aided Design
%V 21
%N 10
%P 611-18
%D Dec. 1989

%T An Efficient Heuristic Procedure for Partitioning Graphs
%A B. W. Kernighan
%A S. Lin
%J Bell Systems Technical Journal
%V 49
%N 2
%D 1970
%P 291-307
------------------------------------------------------------------------------
Paul Hatcher			PHONE    +44 904 432771
Department of Computer Science	JANET    paulh@uk.ac.york.minster
University of York		INTERNET paulh@minster.york.ac.uk
Heslington, York, Y01 5DD	UUCP	 {mcsun,uknet}!minster!paulh
From: west@symcom.math.uiuc.edu (Douglas West)
Newsgroups: comp.theory
Subject: Re: Round robin problem
Date: 20 Aug 92 23:41:47 GMT
Article-I.D.: news.BtB35o.J5
Organization: University of Illinois at Urbana

clin@eng.umd.edu (Charles Lin) writes:
>   Sorry, if this is the wrong place to post.
>   Anyone know of a solution to the following problem:
>   Given a complete graph of n nodes (vertices) where n is even, 
>and given n - 1 colors, color the edges so that:
>   each vertex has at least one edge with each of the n - 1 colors

This is the problem of showing that K_{2n} is 1-factorable.
It is exercise 5.1.5a and exercise 6.2.1 in the graph theory book of
Bondy and Murty.  The standard construction is in the back of the book.
Put one vertex at the center of a ring of 2n-1 others.  Each matching
consists of one radius and the pairs inducing chords perpendicular to it.
-Doug West
Newsgroups: comp.theory
From: chasman@athena.mit.edu (David Chasman)
Subject: TRIVIAL QUESTION FROM AN IGNORANT CHEMIST
Keywords: graph,embedding
Organization: Massachusetts Institute of Technology
Date: Wed, 12 Aug 1992 22:38:38 GMT

I have the following problem.  I have a bunch of verticies and I know
which edges of the completely connected graph exist.  For a graph of
this sort, is there a simple way to compute the minimum embedding
dimension?  e-mail replies appreciated.

--David Chasman
From: watanabe@cs.titech.ac.jp (Osamu Watanabe)
Newsgroups: comp.theory
Subject: ISAAC'92 ERRATUM
Date: 21 Aug 92 00:37:46 GMT
Distribution: comp
Organization: Tokyo Institute of Tech., Dept. of Computer Science, Japan


----- ERRATUM ----

ISAAC '92
(International Symposium on Algorithms & Computation)
(December 16-18, 1992, Nagoya, Japan)

There was a mistake in the last announcement on the ISAAC '92.

>II. FOR FUTHER INFORMATION
>
>The symposium guide including registration form is available via e-mail.
>For recieving the guide, please send e-mail to issac@cs.titech.ac.jp
                                                ^^^^^^^^^^^^^^^^^^^^^

The above e-mail address is wrong, and a correct one is

            isaac@cs.titech.ac.jp
            ^^^^^

Sorry!
Osamu Watanabe
Newsgroups: comp.theory
From: victor@watson.ibm.com (Victor Miller)
Subject: Re: Pippenger's address
Date: Tue, 18 Aug 1992 13:59:26 GMT
Reply-To: victor@watson.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM, T.J. Watson Research Center

>>>>> On Tue, 18 Aug 1992 03:23:40 GMT, cubric@cs.mcgill.ca (Marija Cubric) said:

Marija> Does anybody know an email address of dr. Nicholas Pippenger?

Marija> Marija Cubric.

It's nicholas@cs.ub.ca.

--
			Victor S. Miller
			Vnet and Bitnet:  VICTOR at WATSON
			Internet: victor@watson.ibm.com
			IBM, TJ Watson Research Center
Newsgroups: comp.theory
From: guha@sprecher.cs.uwm.edu (Dr. Sumanta Guha)
Subject: FOCS proceedings
Organization: University of Wisconsin, Milwaukee
Date: Thu, 13 Aug 1992 20:53:08 GMT

Thank you,
Sumanta Guha
EE & CS    
UW-Milwaukee
From: lavinus@csgrad.cs.vt.edu (Joseph Lavinus)
Newsgroups: comp.theory
Subject: Multiple-Way Graph Partitioning refs?
Date: 19 Aug 92 17:23:19 GMT
Organization: VPI&SU Computer Science Department, Blacksburg, VA

I am looking for references on k-way graph partitioning (k > 2).  The only
ones I know of are:

  Sanchis, Laura, "Multiple-Way Network Partitioning," IEEE Transactions on
    Computers, 38: 62-81, 1989.

And various mentions in papers on 2-way partitioning papers on ways to use
2-way algorithms for multiple-way partitioning (such as recursive
decomposition).

Does anyone know of other references on this topic?

Thanks in advance,

Joe
-- 
______________________________________________________________________________
 Joseph W. Lavinus (2816), Virginia Tech             email: lavinus@cs.vt.edu
        "Few NP-hard problems remain difficult when restricted, say,
           to the class of 1-vertex graphs." --- David S. Johnson
Newsgroups: comp.theory,comp.misc
From: volker@vlsivie.tuwien.ac.at (Volker Hamann)
Subject: Determinizing non-deterministic finite automata
Reply-To: volker@vlsivie.tuwien.ac.at (Volker Hamann)
Organization: Technical University of Vienna
Date: Fri, 21 Aug 1992 08:15:42 GMT

Hello!

In the course of implementing regular expression search in hardware, a
necessity to making non-deterministic finite-state automata deterministic
has arised.
Has anybody heard of available software performing this task and probably
even minimizing the resulting deterministic automaton? What are the interfaces
to this software if any (input/output format, etc.)?
I am grateful for any response.

Regards,

	Volker
--
|   /| ! Volker Hamann              ! Email: volker@vlsivie.tuwien.ac.at
|  / | ! Department for VLSI Design ! Phone: (++43 1) 58801-8142
|-/--| ! University of Technology   ! Fax:   (++43 1) 569697
|/   | ! Vienna, Austria              "IS THERE ANYBODY OUT THERE?"
Newsgroups: comp.theory
From: cubric@cs.mcgill.ca (Marija Cubric)
Subject: Pippenger's address
Organization: SOCS, McGill University, Montreal, Canada
Date: Tue, 18 Aug 1992 03:23:40 GMT

Does anybody know an email address of dr. Nicholas Pippenger?

Marija Cubric.

Newsgroups: comp.theory
From: orpheus@reed.edu (P. Hawthorne)
Newsgroups: comp.theory
Subject: A Graph Theory Newsgroup, Perhaps?
Date: 18 Aug 92 08:49:14 GMT
Article-I.D.: reed.1992Aug18.084914.27141
Organization: Reed College, Portland OR


  Graph theory is at the heart of so many fields that it is somewhat
obscured by its own versatility.

  I feel that there ought to be a graph theoretic newsgroup, if only for
the insights that such a multidisciplinary newsgroup could offer.

  I'd be interested in hearing from others, to see if a more formal
approach to creating such a newsgroup is warranted.


  Theus (Prometheus Hawthorne - Jones, orpheus@reed.edu)
Newsgroups: comp.theory
From: beigel-richard@CS.YALE.EDU (Richard Beigel)
Newsgroups: comp.theory
Subject: new phone number for Richard Beigel
Date: 21 Aug 92 19:18:27 GMT
Reply-To: Richard Beigel <beigel-richard@CS.YALE.EDU>

Dear colleagues:

As of today my office phone number is (203)432-1228.  My new office is
#401, Watson hall.

My mailing address at Yale is unchanged:

	Richard Beigel
	Dept. of Computer Science
	51 Prospect Street
	P.O. Box 2158, Yale Station
	New Haven, CT  06520-2158

As of September 1, my home address and phone number will be:

	112 Bishop St.
	New Haven, CT  06511
	(203)777-1019

(There is no relation between the two moves.)

Sincerely,
Richard Beigel
beigel-richard@cs.yale.edu
Newsgroups: comp.theory
From: cscc13@judy.uh.edu (NAVEED IQBAL)
Subject: Re: Generic sorting functions
News-Software: VAX/VMS VNEWS 1.41    
Organization: University of Houston
Date: Sat, 22 Aug 1992 04:52:00 GMT

In article <9208212151.AA44579@cs90code.csv-tgsc.amex-trs.com>, gonzalod@amex-trs.com (Gonzalo Diethelm) writes...
> 
> 
>Distribution: world
> 
>Hello everyone,
> 
>A very generic question. Given a set S of n strings (the `|' characters
>are used as delimiters):
> 
>  s1   |dunno|
>  s2   |I'd rather have a bottle in front of me than a frontal lobotomy|
>  s3   |eschew clever rules|
>  ... ...
>  sn   |bzzzzt!|
> 
>and an ordering sequence O:
> 
>  {s4, s1, s6, s2, sn, s3, ... s7}
> 
>is there any way to determine a fixed, hopefully cheap function
> 
>  f(): SxS -> integers
> 
>with the property that
> 
>  if si comes before sj in O, f(si, sj) < 0
>  if si comes after  sj in O, f(si, sj) > 0
> 
>that is, could be used to sort the strings in the given sequence?


	I'm no master programmer but couldn't you use some recursion to
sort the strings individually....maybe pushing the characters at every 
stage and then popping ans comparing.

I think I lost you, in which case...disreagrd this posting.

Naveed
From: crepeau@iro.umontreal.ca (Claude Crepeau)
Newsgroups: comp.theory
Subject: Special Issue on ZERO-KNOWLEDGE of the Journal of CRYPTOLOGY
Date: 17 Aug 92 09:14:54 GMT
Reply-To: Theory-A - TheoryNet World-Wide Events <THEORY-A%NDSUVM1.BITNET@cmsa.Berkeley.EDU>,
        Claude Crepeau <crepeau@iro.umontreal.ca>


                                Final Annoucement
                           for the Journal of CRYPTOLOGY's

********************************************************************************
*                                                                              *
*                         SPECIAL ISSUE on ZERO-KNOWLEDGE                      *
*                                                                              *
********************************************************************************

Authors are encouraged to submit original material for publication in the
special issue on zero-knowledge. Submission deadline is September 1st 1992.
Papers should be submitted to any of the following two addresses since I am
currently sharing my time between Montreal and Paris, or by email in LaTeX
to  crepeau@dmi.ens.fr  or  crepeau@iro.umontreal.ca .

I look forward to getting your papers.

                                                Claude Crepeau
                                                Special Issue Editor


-------------------------------------------------------------------

        PARIS                                   MONTREAL

Ecole Normale Superieure                Universite de Montreal
Dep. de Mathematiques-Informatique      Dep. d'Informatique et R.O.
Pavillon, bureau P3                     C.P. 6128, succursale ''A''
45 rue d'Ulm                            Montreal (Quebec)
75230 Paris CEDEX-05                    Canada  H3C 3J7

-------------------------------------------------------------------
Newsgroups: comp.theory
From: bright@apollo.cs.jhu.edu (Jonathon Bright)
Subject: SODA and SPAA proceedings
Organization: Johns Hopkins Computer Science Department, Baltimore, MD
Distribution: usa
Date: Thu, 13 Aug 1992 18:10:10 GMT

Hi everyone.
I'd like to acquire the proceedings to the
first SODA and SPAA conferences.
Please email me if you would be willing to sell
me a copy of either of these.

Thanks,

Jon Bright