Descriptive complexity, bounded set theory and Web-like databases

Vladimir Sazonov
Russian Acad. of Sci.

This is an overview lecture 1) on descriptive complexity theory via (flat) finite model theory and 2) on extending this approach to the case of (nested) hereditarily-finite sets or hypersets satisfying Aczel's antifoundation axiom. The corresponding bounded set-theoretic (BST) language Delta will be treated also as a query language to Web-like databases (i.e. semistructured, nested, cyclic DB represented as graphs, including the real WWW). Original results of the author will be presented (including, if the time will permit, proof theoretic conservativity and independence results related to BST and "P=NP?").

Back to seminar homepage