DIMACS TR: 97-21
Bounded Hyperset Theory and Web-like Data Bases
Authors: Alexei Lisitsa and Vladimir Sazonov
ABSTRACT
It is demonstrated how a Hyperset Theory (satisfying P.Aczel's
Anti-Foundation Axiom) naturally arises from the idea of World-Wide Web
(WWW). Alternatively, Web serves as an illustration and possible
application of the abstract notion of antifounded sets. A
$\Delta$-language of Bounded Hyperset Theory is presented as a query
language to the Web or, more generally, to Web-like Data Bases (WDB). It
is shown that it describes exactly all abstract (or generic, up to
bisimulation) PTIME-computable queries with respect to (possibly cyclic)
graph encoding of hypersets. This result is based (i) on reducing of the
$\Delta$-language for hypersets to the language FO+LFP ( = First-Order
Logic with the Least Fixed-Point operator) over graphs considered up to
bisimulation relation and (ii) on definability in FO+LFP of a linear
ordering on any strongly extensional finite graph by a single formula
(cf.\ also DIMACS TR-97-05). The case of finitely branching, possibly
infinite graphs and corresponding hypersets is also discussed. It
corresponds to finitely-branching, but infinite Web. However, it deserves
special further investigation.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-21.ps.gz
DIMACS Home Page