Article View: comp.lang.prolog
Article #1827Cyclic structures (was general data structures are [not] impossible)
From: Mark Johnson
Date: Mon, 18 Feb 1991 12:41
Date: Mon, 18 Feb 1991 12:41
14 lines
1236 bytes
1236 bytes
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
Technical Details
Message-ID:
<4073@scott.ed.ac.uk>Path:
arc1-ca.pugleaf.net!utzoo!mnetor!tmsoft!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!ukc!edcastle!edcogsci!johnsonReferences:
<6406@skye.cs.ed.ac.uk>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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