Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!husc6!sri-unix!teknowledge-vaxc!uw-beaver!cornell!svax!belmonte From: belmonte@svax.UUCP Newsgroups: comp.ai Subject: Re: Network Complexity Message-ID: <1011@svax.cs.cornell.edu> Date: Tue, 24-Feb-87 22:56:45 EST Article-I.D.: svax.1011 Posted: Tue Feb 24 22:56:45 1987 Date-Received: Fri, 27-Feb-87 04:57:28 EST References: <292@ihnp3.UUCP> Reply-To: belmonte@svax.cs.cornell.edu (Matthew Belmonte) Followup-To: comp.ai Distribution: world Organization: Cornell Univ. CS Dept. Lines: 30 Keywords: graph theory, computer networks, brain hurts Summary: another application (I think) In article <292@ihnp3.UUCP> mth@ihnp3.UUCP (Mark Horbal) writes: > If we define the "complexity" of a computer network as a > measure of difficulty in observing, understanding, and > excercising a modicum of control over it, how is this > "complexity" estimated? > > If we further choose a simple but intuitive way of representing > a computer network by a graph, how do we quantify this "complexity" > with respect to the graph's topology? I believe there might be another area which is relevant to the problem you mention in the second statement above, but not the first. A year ago I was doing an internship at NRL implementing a transition-network parser for some context-free grammars which mimicked *small* subsets of English. The question occurred to me, "how does one quantify the complexity of the transition networks we generate?" (By "complexity" here I mean topics such as: Do we have a lot of long paths consisting of nonterminals which will result in many failed parses? Do we have many null transitions that we can't squeeze out by munging adjacent states together? etc.) The answer I got was, well, we don't really know of any method of completely characterising such complexities. Is this the same sort of problem as mentioned above, or am I completely off-base? Disclaimer: Yes, I know I'm extraordinarily weak on theory, but I'm a lowly, simple-minded freshman, so I have an excuse. -- "When you've got them by the balls, their hearts and minds will follow." -- a member of the Nixon administration Matthew Belmonte Internet: BITNET: UUCP: ..!decvax!duke!duknbsr!mkb