Path: utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!edcastle!edcogsci!johnson
From: johnson@cogsci.ed.ac.uk (Mark Johnson)
Newsgroups: comp.lang.prolog
Subject: Cyclic structures (was general data structures are [not] impossible)
Summary: Prolog needs either cyclic structures or arrays
Message-ID: <4073@scott.ed.ac.uk>
Date: 18 Feb 91 12:41:23 GMT
References: <6406@skye.cs.ed.ac.uk>
Reply-To: johnson@scott.UUCP (Mark Johnson)
Organization: Centre for Cognitive Science, Edinburgh, UK
Lines: 14

Of course, any cyclic structure can be "broken up" into an acyclic
structure by naming its nodes (say, with numbers) and storing their 
values in some sort of array.  For some applications the packages
in the standard libraries that run in n lg n time are satisfactory,
but for, say, dealing with larger FSAs the non-constant access
time is too great a price to pay.  (Asserting the relevant facts
into the database can give almost constant time access, but at
the high cost of assertion, not to mention the abandonment of
the simple logical semantics).

Cyclic structures allow DFSAs to be implemented so that following
an arc can be performed in constant time. 

Mark