Vladimir Sazanov

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.

Abstract:

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.)