🚀 go-pugleaf

RetroBBS NetNews Server

Inspired by RockSolid Light RIP Retro Guy

Article View: comp.lang.prolog
Article #1827

Cyclic structures (was general data structures are [not] impossible)

#1827
From: Mark Johnson
Date: Mon, 18 Feb 1991 12:41
14 lines
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!johnson
References: <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