Path: utzoo!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!spool.mu.edu!munnari.oz.au!comp.vuw.ac.nz!steve
From: steve@comp.vuw.ac.nz (Steve Cassidy)
Newsgroups: comp.lang.prolog
Subject: Re: Partial Orders
Message-ID: <1991Mar05.021953.11576@comp.vuw.ac.nz>
Date: 5 Mar 91 02:19:53 GMT
References: <13048@darkstar.ucsc.edu>
Sender: news@comp.vuw.ac.nz (News Admin)
Organization: Dept. of Comp. Sci., Victoria Uni. of Wellington, New Zealand.
Lines: 43
Nntp-Posting-Host: climie.comp.vuw.ac.nz

Gerard Ellis writes:
>
>This transitive closure representation uses O(n^2) space.
>While a dag representation of the non-transitive representation of a poset is 
>still O(n^2), it uses a subset of the space of the transitive dag. 

I chose to store the transitive dag to make the traverse operation faster,
having just thought about it some more, it doesn't have that effect.  However,
it makes deletion a whole lot simpler and in my case the space cost 
isn't the problem.  

>Before we could help you further we need to know the structure of the
>terms in the poset. As Richard O'Keefe pointed out: ordering sets by
>cardinality also ordered them by inclusion.  Similarly, cardinality can
>be used for graphs. However, terms such as semantic networks which have
>abstraction over terms, size is not a necessary condition.  Size is
>still only a very coarse first step.

My terms look like:      447:[class24]/[a]/[class42, e, #]/[ey]
                      RuleNo:LeftContext/Graph/RightContext/Phon

as I said, they are rules for translating text to speech. The ordering is on
generality, more general rules apply to a superset of the text strings that
the less general rules apply to.  Two rules can be orthogonal if the sets of
strings that they cover don't overlap; they might also be 'equal', if the sets
overlap -- although in my application this shouldn't occur.  The classes above
are just sets of letters, eg class24 = |cfhl|.  

Thanks for the pointers, I may chase them if I need a speedup.  The stuff I've
written already, as described before, gives me usable performance.  My
application is learning the above rules from examples and I can get through
500 examples in 20-30 min.  This is sufficient for my purposes.  (However, if
there is an obvious speedup that occurs to somebody, please let me know!)

Thanks again, 

Steve Cassidy
==========================================================
Computer Science,                     steve@comp.vuw.ac.nz
Victoria University of Wellington,    ====================
Box 600,                              Voice:  +64 4 715328
Wellington, New Zealand.              Fax:    +64 4 712070
----------------------------------------------------------