Program Systems Institute, Russian Academy of Sciences
On Computability over Hereditarily-Finite Sets in Logarithmic Space
- DIMACS Center - Room 431
- Busch Campus
- Piscataway, New Jersey
- February 16, 2:30 P.M.
We discuss several versions of a set theoretic $\Delta$-language as a
reasonable prototype for ``nested'' data base query language where
data base states and queries are considered, respectively, as
hereditarily-finite sets and set theoretic operations. In a previous
work such a language exactly corresponding to PTIME-computability was
introduced. It is supposed that HF-sets are naturally presented by
acyclic pointed graphs. Here we consider a number of languages for
sub-PTIME computable set operations via corresponding graph
transformers. Two such languages lead to a notion of NLOGSPACE and,
respectively, DLOGSPACE computable queries over HF which appear the
most natural, at our present knowledge, among others considered here.
Unlike the ``flat'' relational data bases the problem of finding
sufficiently good corresponding approach for HF proves to be more
intricate and, furthermore, gives rise to some interesting questions
in finite model theory.
(The talk is based on a work in cooperation with A.Lisitsa.)