HDTenEightyP/NetNews huggingface dataset:
From: Kevin.D.Brunson.1@nd.edu (Kevin D. Brunson)
Newsgroups: comp.theory
Subject: Matrix Square Root
Date: 8 Sep 92 23:27:08 GMT
Organization: Notre Dame


		This is the first message I have posted to this service so I hope that
this is the most appropriate group.  
		The problem I have seems like a simple one:  How do I calculate the
square root of a symetric matrix?  Theoretically, if a matrix A is positive
semidefinite then there exists a matrix B that is the square root of A such
that A = B*B.  I have consulted Lancaster and Tismenetsky's "The Theory of
Matrices" but a programmable algorithm is not obvious.  The matrix I have
generated in monte carlo experiments is 10 x 10 but I could use a smaller
one if I could find an operationalization of a method.  
		Hope I hear from someone.	

Kevin Brunson
Newsgroups: comp.theory
From: mdhutton@cs.toronto.edu (Mike Hutton)
Subject: Re: What kind of an automaton is this?
Organization: Department of Computer Science, University of Toronto
Date: 11 Sep 92 16:37:11 GMT

In article <4QU69WW@math.fu-berlin.de> dww@inf.fu-berlin.de writes:
>We've been discussing on comp.compilers the kind of parsing automaton that is described in
>DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
>learned about when I studied Automata Theory with the next state and the
>output being determined by the current state, the top of the stack, and
>the current symbol in the input. In this "strange" automaton the lhs of
>the production being reduced is returned to the input after the stack
>has been popped. This is not just backing up over input, but non-terminals
>can be built up on the input, perhaps with a number of epsilon productions.
>Some people have said "oh yes, we like that and have a hack to use it"
>but it is unclear what exactly the computational complexity of this
>automaton is. LR parsing is clearly a subset of what this automaton can
>do - just don't do any of the strange reductions. 
>
>Has anyone encountered this type of automaton before? What does it buy
>me, i.e. what special problems could be solved with this type of
>automaton that we can't do with LR-parsers? Pointers or ideas of
>any kind are welcome.
>

You state SLR differently than I have seen it before; are you thinking
of noncanonical SLR [Tai 1979]?  

Fischer and LeBlanc (Crafting a Compiler) defines the SLR(1) machine as
an extension of the LR(0) machine to include one symbol of (canonical,
i.e. temrminal symbols only) lookahead (but no new states); LALR(1) is
a reduction of the full LR(1) machine to merge redundant states.  Both
are attempting to gain the expressiveness of the LR(1) machine with
cost closer to the LR(0) machine, just from different directions.

SLR parsers are still canonical parsers though; I don't see how the
description given above matches with the definition in Fischer and
LeBlanc or with my memory.  

To disagree with the previous two responses, even if you extend to allow
noncanonical lookahead (i.e. allow 2 stacks to go through the
input and put nonterminals back on the input stack), you still have a
context-free-like grammar (just with a more powerful lookahead 
ability) defining the language.  That the noncanonical parser *uses* two 
stacks doesn't imply that any language acceptable by an arbitrary
2-stack automaton (i.e. Turing Machine) can be expressed with an appropriate 
NLR(k) or NSLR(k) grammar---you still have k-bounded lookahead, even if 
it can also include nonterminals.

The point of noncanonical extensions was firstly to allow grammars to
be written more "naturally" (no contortions to make them LALR(1) parsable)
not really to extend the class of recognizable languages.  However, you
can get some non-LR(k) (non DCFL) languages with noncanonical parsers, and
this would be useful for some language constructions.

I wrote a grad-course paper surveying this about 3 years ago which
has most of the relevant references; if still interested send email.  

Newsgroups: comp.theory
From: frank@Cookie.secapl.com (Frank Adams)
Subject: Re: What kind of an automaton is this?
Date: Fri, 11 Sep 1992 20:39:51 GMT
Organization: Security APL, Inc.

In article <92Sep11.123701edt.47914@neat.cs.toronto.edu> mdhutton@cs.toronto.edu (Mike Hutton) writes:
>In article <4QU69WW@math.fu-berlin.de> dww@inf.fu-berlin.de writes:
>>We've been discussing on comp.compilers the kind of parsing automaton that is described in
>>DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
>>learned about when I studied Automata Theory with the next state and the
>>output being determined by the current state, the top of the stack, and
>>the current symbol in the input. In this "strange" automaton the lhs of
>>the production being reduced is returned to the input after the stack
>>has been popped. This is not just backing up over input, but non-terminals
>>can be built up on the input, perhaps with a number of epsilon productions.
>
>To disagree with the previous two responses, even if you extend to allow
>noncanonical lookahead (i.e. allow 2 stacks to go through the
>input and put nonterminals back on the input stack), you still have a
>context-free-like grammar (just with a more powerful lookahead 
>ability) defining the language.  That the noncanonical parser *uses* two 
>stacks doesn't imply that any language acceptable by an arbitrary
>2-stack automaton (i.e. Turing Machine) can be expressed with an appropriate 
>NLR(k) or NSLR(k) grammar---you still have k-bounded lookahead, even if 
>it can also include nonterminals.

This is correct as far as it goes.  However, as I noted, the machine *can*
in fact perform (almost) arbitrary stack operations on the two stacks.  (The
pushdown-machine stack cannot be left empty, but this is a detail.)  To get
full Turing-machine compatibility, you have to encode the Turing-machine
state in the symbols on top of the stacks; this gets messy, but is quite
doable.

To approach it in terms of the lookahead, you can look ahead more than k
symbols by shifting input symbols onto the stack, deciding what you want to
do, and then moving those symbols back to the input via unit productions.
What you push back may not be *exactly* what you originally read, but it can
function like what you originally read for subsequent processing.

(If k=0, the situation is quite different.  In this case, the symbol on top
of the stack after a special reduction must be a shift state, since a shift
was done in it before (unless this is an epsilon-production; but then an
infinite loop ensues).  Hence the next operation will be a shift, and you
might as well have just put the lhs on the stack in the first place.
However, 0-symbol lookahead pdm's are not very practical.)
Newsgroups: comp.theory
From: weberwu@inf.fu-berlin.de (Debora Weber-Wulff)
Subject: What kind of an automaton is this?
Reply-To: dww@inf.fu-berlin.de
Organization: Free University of Berlin
Date: Wed, 9 Sep 1992 13:13:57 GMT

We've been discussing on comp.compilers the kind of parsing automaton that is described in
DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
learned about when I studied Automata Theory with the next state and the
output being determined by the current state, the top of the stack, and
the current symbol in the input. In this "strange" automaton the lhs of
the production being reduced is returned to the input after the stack
has been popped. This is not just backing up over input, but non-terminals
can be built up on the input, perhaps with a number of epsilon productions.
Some people have said "oh yes, we like that and have a hack to use it"
but it is unclear what exactly the computational complexity of this
automaton is. LR parsing is clearly a subset of what this automaton can
do - just don't do any of the strange reductions. 

Has anyone encountered this type of automaton before? What does it buy
me, i.e. what special problems could be solved with this type of
automaton that we can't do with LR-parsers? Pointers or ideas of
any kind are welcome.

-- 
Debora Weber-Wulff                       dww@inf.fu-berlin.de
Institut fuer Informatik                 +49 30 89691 124
Nestorstr. 8-9                           (INCLUDE "standard.disclaimer")
D-W-1000 Berlin 31                       (PRINTN (WITTY-MESSAGE TODAY))
Newsgroups: comp.theory
From: markjan@cs.kun.nl (Mark-Jan Nederhof)
Subject: Re: What kind of an automaton is this?
Organization: University of Nijmegen, The Netherlands
Date: Thu, 10 Sep 1992 16:04:04 GMT

In <4QU69WW@math.fu-berlin.de> weberwu@inf.fu-berlin.de (Debora Weber-Wulff) writes:

  >We've been discussing on comp.compilers the kind of parsing automaton that 
  >is described in
  >DeRemer[CACM 71] as being an SLR-Parser. It is not the kind of PDA I
  >learned about when I studied Automata Theory with the next state and the
  >output being determined by the current state, the top of the stack, and
  >the current symbol in the input. In this "strange" automaton the lhs of
  >the production being reduced is returned to the input after the stack
  >has been popped. This is not just backing up over input, but non-terminals
  >can be built up on the input, perhaps with a number of epsilon productions.
  >Some people have said "oh yes, we like that and have a hack to use it"
  >but it is unclear what exactly the computational complexity of this
  >automaton is. LR parsing is clearly a subset of what this automaton can
  >do - just don't do any of the strange reductions. 

Being allowed to push symbols onto the input is similar to having two 
stacks. Having two stacks is again similar to having a tape on which you 
can read, write and move both ways; in other words, to having a Turing machine.
 
  >Has anyone encountered this type of automaton before? What does it buy
  >me, i.e. what special problems could be solved with this type of
  >automaton that we can't do with LR-parsers? Pointers or ideas of
  >any kind are welcome.

The class of Turing-decidable languages is the largest class of
decidable languages that we know. It subsumes the class of LR(k) languages 
and many others.

translation, and compiling.

Mark-Jan Nederhof
University of Nijmegen
From: skow@cs.utwente.nl (Jacek Skowronek)
Newsgroups: comp.theory
Subject: Fixed point semantics
Date: 7 Sep 92 15:27:38 GMT
Organization: University of Twente, Dept. of Computer Science

What does it mean when "a language gives a least fixed point semantics".

Jacek

-- 
-------------------------------------------------------------------
Jacek Skowronek				e-mail: <skow@cs.utwente.nl>
Departament of Computer Science
Twente University
Enschede, The Netherlands
From: fs@cs.tulane.edu (Frank Silbermann)
Newsgroups: comp.theory
Subject: Re: Fixed point semantics
Date: 11 Sep 92 17:17:25 GMT

Nntp-Posting-Host-[nntpd-4753]: caesar
Organization: Computer Science Dept., Tulane Univ., New Orleans, LA
Date: Fri, 11 Sep 1992 17:14:38 GMT


skow@cs.utwente.nl
Jacek Skowronek:
>>		What does it mean when "a language gives
>>		a least fixed point semantics"?

<1992Sep9.065818.9053@odin.diku.dk> rose@diku.dk
(Mads Rosendahl):
>	Fixed Point Semantics is often used for the kind
>	of Denotational Semantics which is based on Domain Theory

Stoy writes that Scott invented Domain Theory to give
Denotational Semantics on a firm mathematical foundation.
So what kind of denotational semantics is _not_ based
(at least implicitly) on domain theory?

>	and where one does not require the semantics in some sense
>	to be computable (ie. based on the lambda calculus).

It is my impression that the language of Domain Theory
_is_ a lambda notation, albeit one that was specifically
created to represent elements of a pre-conceived mathematical
model (the domain).

As for Domain Theory not being computable, I thought the notion
of _continuity_ (a notion which permeates domain theory)
which was motivated by the desire to ensure computability.

If you rely only on continuous operations over continuous
domains, then how can the semantics be uncomputable?
Chapter 10 of David Schmidt's text discusses work
by Uwe Pleban and others on use of denotational semantics
as an interpreter-generator.

------------------------------------------
Frank Silbermann	fs@cs.tulane.edu
Tulane University	New Orleans, Louisiana  USA
From: samir@cs.umd.edu (Samir Khuller)
Newsgroups: comp.theory
Subject: Workshop on Approximation Algorithms (Dec 1992)
Date: 8 Sep 92 17:51:47 GMT
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742



           Program for Workshop on Approximation Algorithms
                   
                       December 16 & 17, 1992

                 Indian Institute of Technology, 
			New Delhi, INDIA


Wednesday, December 16, 1992

	9.30am to 10.30 am
	Proof verification and the hardness of approximations, I
	Madhu Sudan (U.C. Berkeley and IBM)

	11am to 12 noon
	Proof verification and the hardness of approximations, II
	Madhu Sudan (U.C. Berkeley and IBM)

	12 noon to 2pm
	Lunch

	2pm to 3pm
	On the approximation of graph coloring and set cover problems
	Mihalis Yannakakis (AT&T Bell Labs)

	3.30pm to 4.30pm
	Good, better and best approximation algorithms.
	Dorit Hochbaum (U.C. Berkeley)


Thursday, December 17, 1992

	9am to 10am
	On the approximation of maximum satisfiability
	Mihalis Yannakakis (AT&T Bell Labs)

	10.30am to 11.30am
	Adapting the classical primal-dual framework to 
	approximation algorithms	
	Vijay Vazirani (IIT Delhi)

	12 noon to 1pm
	Markov chains, random generaration, and approximate counting.
	Umesh Vazirani (U.C. Berkeley)

	1pm to 2.30pm
	Lunch

	2.30pm to 3.30pm
	Rapid mixing arguments for matroids.
	Milena Mihail (Bellcore)

	4pm to 5pm
	Random walks in convex sets            
	Ravi Kannan (Bellcore and CMU)


Note: Registration information for the workshop will be sent along
with that for the FSTTCS conference.

For more information contact Vijay Vazirani (vazirani@cse.iitd.ernet.in)
From: dawar@saul.cis.upenn.edu (Anuj Dawar)
Newsgroups: comp.theory
Subject: A question about finite automata
Keywords: finite automata, languages
Date: 10 Sep 92 01:39:53 GMT
Organization: University of Pennsylvania

I have a problem relating to finite automata that I would appreciate 
help with.

Let A and B be two non-deterministic finite automata, each with n 
states, over the same alphabet.  It is easy to see that if they 
agree on all strings of length at most 2n, then they accept the same
language.  However, the automata that I am interested in have some 
special properties, and I was wondering if these constraints could 
be used to reduce that 2n bound (I am particularly interested in 
obtaining a sub-linear bound).

The relevant properties are:

1) Every state is a final state, i.e. the languages accepted are
prefix closed.

2) A and B can be seen as two copies of the same automaton, differing
only in the choice of starting state.  In other words, I am actually
interested in the equivalence of states, rather than that of automata.

3) There is a constant k, such that the transition graphs of the automata
have diameter k, i.e. there is a path from any state to any other state
of length at most k.  Recall that the automata are non-deterministic.

My intuition suggests that 1 and 2 would not make much difference, except
for getting rid of the factor of 2, but the third constraint might help.
I would appreciate any help, or any pointers to literature that might be
relevant.

Note: I am not particularly interested in the computational complexity
of determining equivalence, but in an upper bound on the length of the
shortest string that will distinguish two states.

 -Anuj Dawar
  dawar@saul.cis.upenn.edu
Newsgroups: comp.theory.dynamic-sys
From: wilcox@erc.cat.syr.edu (Maynard Wilcox)
Subject: Re: Chaos Programs by Holden and Muhamad
Keywords: chaos, differential systems, programs
Organization: Electronic Resource Center, Syracuse
Date: Sat, 12 Sep 92 21:58:08 EDT

In article <1992Sep11.134420.19454@cci632.cci.com> dwp@cci632.cci.com (Dana Paxson) writes:
>I am trying to track down some software written to illustrate chaotic
>behavior as described in the book CHAOS, edited by Arun V. Holden,
>copyright Manchester University Press 1986, published in the USA by
>
>
>3)	What other such tools may be available;
>
>4)	Whether this is the right place to post this request.
>
 In answer :
 Differential and Difference Equations through Computer Experiments
    with Diskette containing PHASER ( an animator/simulator for
    Dynamical systems for IBM personal computers )
 by Huseyin Kocak      2nd Edition  copyright 1986,1989
 from Springer-Verlag  ISBN 3-540-96918-7 



and yes :-)
From: park@netcom.com (Bill Park)
Newsgroups: comp.theory.dynamic-sys
Subject: Re: metric entropy
Summary: Chaos and Order in the Capital Markets
Keywords: Fractals, chaos, fractal dimension
Date: 7 Sep 92 19:01:05 GMT
Followup-To: comp.theory.dynamic-sys
Organization: Netcom - Online Communication Services  (408 241-9760 guest)

In article <1488@srtp.UUCP> bernard@srt-poste.fr writes:

> I'm looking for references of methods for calculating an estimation of
> fractal dimension of data sets
>	B. Lemarie

Edgar E. Peters, <Chaos and Order in the Capital Markets.  A New View
     of Cycles , Prices, and Market Volatility>, New York, John Wiley
     & Sons, Inc., ISBN 0-471-53372-6 (1991).

The section entitled "The Fractal Dimension" (pp. 155-157, in Chapter
12, "The Dynamical Analysis of Time Series") describes the correlation
integral, which the author describes as "A similar, more practical
method [than estimating the fractal dimension graphically by covering
the contour with circles and computing the fractal dimension D as

     D = log(N) / log(1/R), where
     N = number of circles of diameter R.]

"The correlation integral Cm(R) is the probability that a pair of
points in the attractor [Peters is discussing the measurement of the
fractal dimension of an attractor in a phase space of a chaotic
system] is within a distance R of one another."

Peters also discusses the Hurst dimension, which is the reciprocal of
the fractal dimension, and shows how to determine it using a different
graphical procedure.

Finally, Peters gives several listings of short computer programs for
various kinds of nonlinear analyses, all in the BASIC language.  One
of them calculates Cm(R) from a data series of up to 2,000 values.

Peters' book is also the best I've found so far on nonlinear dynamics
applied to analysis of financial time series.

Another excellent book on nonlinear topics is:

Manfred Schroeder, <Fractals, Chos, Power Laws.  Minutes from an
     Infinite paradise>, U.S.A., W. H. Freeman and Company, 
     ISBN 0-7167-2136-8 (1991).

Schroeder discusses fractal dimensions in at least nine different
places in this book.  The treatments are very brief in comparison to
Peters' book, but is a much broader work that shows the relationships
of such concepts from the point of view of a polymath who is
comfortable in physics, mathematics, engineering, and biology.

Bill Park
=========
-- 
Grandpaw Bill's High Technology Consulting & Live Bait, Inc.
Newsgroups: comp.theory.dynamic-sys
From: prabhu@cae.wisc.edu (Vittaldas Prabhu)
Subject: Re: Chaos Programs by Holden and Muhamad
Organization: U of Wisconsin-Madison College of Engineering
Date: 11 Sep 92 13:45:59 CDT
Keywords: chaos, differential systems, programs


It may be worth while to look at Proceeding of IEEE, Aug 1987,
which was a special issue on Chaotic Systems. There is paper
"INSITE - A Software Toolkit for analysis of nonlinear systems"
by T.S.Parker and L.O.Chua.

Sorry, I have not used it.

vittal
From: starke@RHRK.UNI-KL.DE (Gerolf Starke)
Newsgroups: comp.theory.dynamic-sys
Subject: Address of J. D. Farmer wanted
Date: 12 Sep 92 20:30:48 GMT
Reply-To: Gerolf Starke <starke@RHRK.UNI-KL.DE>
Distribution: inet
Organization: The Internet

Dear subscribers.

I am searching the e-mail or post address or FAX number of
J. Doyne Farmer. Maybe he works at the Theoretical Division
and Center for Nonlinear Studies, Los Alamos National Laboratory
in Los Alamor, New Mexico.

Thanks for your help in advance,
Gerolf
---
Gerolf J. Starke                              phone: +49/631/205-2128
Institute of Applied Mechanics                internet: starke@rhrk.uni-kl.de
University of Kaiserslautern, 6750            compuserve: 100010,3451
Germany                                       fax: +49/631/205-3055
From: watson@maths.uwa.oz.au (David Watson)
Newsgroups: comp.theory.dynamic-sys
Subject: Re: Specialized software
Date: 11 Sep 1992 00:56:05 GMT
Organization: The University of Westrn Australia
Distribution: inet
NNTP-Posting-Host: madvax.maths.uwa.oz.au

vanadis@cs.dal.ca (Jose Castejon-Amenedo) writes:


>	I am looking for ftpable software for dynamical systems
>research (broadly speaking), mainly (but not exclusively) for
>Unix-based X systems. Can anybody out there please give me a few
>pointers? 


I'm not sure if this is what you have in mind but we have been
developing a program to predict values in a time-series by
embedding in higher dimensions, tesselating, and interpolating.
The tesselation is Delaunay and is practical up to about 5 or 6
dimensions for data sets that are not too large.  Interpolation is
by Sibson's natural neighbour method or various radial basis
functions.  The radial basis procedure is applied to the second
order natural neighbour subset, that is, all the natural neighbours
of the interpolation location and all their natural neighbours.

The program will compile and run under OpenWindows version 3 with
the XView libraries.

This program is still under development and probably still has some
bugs - however, criticism and advice are welcomed.  Updates will
appear at irregular intervals.

ftp    madvax.uwa.edu.au    /pub/dddd/*


--
Dave Watson                          Internet: watson@maths.uwa.edu.au
Department of Mathematics            
The University of Western Australia               Tel: (61 9) 380 3359
Nedlands, WA 6009  Australia.                     FAX: (61 9) 380 1028
From: dwp@cci632.cci.com (Dana Paxson)
Newsgroups: comp.theory.dynamic-sys
Subject: Chaos Programs by Holden and Muhamad
Keywords: chaos, differential systems, programs
Date: 11 Sep 92 13:44:20 GMT
Organization: Computer Consoles Incorporated

I am trying to track down some software written to illustrate chaotic
behavior as described in the book CHAOS, edited by Arun V. Holden,
copyright Manchester University Press 1986, published in the USA by
Princeton University Press.  There is a note facing the inner title
page:

	"A suite of programs by M. A. Muhamad and A. V. Holden that
	illustrate chaotic behavior in maps and in differential
	systems is available to accompany this book:  these programs
	are available only on 40- or 80-track 5.25" discs for the 
	Acorn BBC-B computer.  

	 Maps of the real line, the plane and the complex plane, with
	their associated bifurcation diagrams, strange attractors and
	Julia sets, are presented.  Trajectories, strange attractors,
	and reconstructed strange attractors are presented for
	nonlinear differential systems and forced systems described in
	Chapter 2: by changing the parameters of the equations the
	routes into chaos may be followed.

	 Further information from: Chaos and Strange Attractors,
	Manchester University Press (Software), Oxford Road,
	Manchester M13 9PL, UK."

Before I plunge off to the post office with letter in hand, I would
like to find out:

1)	Whether these programs or more modern transformations of them
	are available via Internet;

2)	Whether the authors use Internet;

3)	What other such tools may be available;

4)	Whether this is the right place to post this request.

Thanks,

Dana Paxson
Network Applications Systems Group
Northern Telecom			Phone:		1 716 654-2588
97 Humboldt Street			Internet:	dwp@cci.com
Rochester, New York  14609		CompuServe:	71201,2213

Disclaimer:  Any opinions expressed above are mine personally, and do 
	     not necessarily reflect the views of my employer.
From: bernard@srt-poste.fr (Bernard Lemarie )
Newsgroups: comp.theory.dynamic-sys
Subject: metric entropy
Date: 7 Sep 92 14:22:54 GMT
Reply-To: bernard@srt-poste.fr
Organization: Service de Recherche Technique de la Poste


		Hello there,

I'm looking for references of methods   for calculating   an estimation  of fractal dimension of data sets . thank's a lot .

	B. Lemarie