Skip to content

LAA

Seminar

A normal form for singulary logic over physically realizable data models

Lindell, S (Haverford College)
Tuesday 28 February 2006, 17:00-17:45

Seminar Room 1, Newton Institute

Abstract

We present a new normal form for first-order logic over bounded-degree structures which relies on the symmetry of labeled connections between elements of the structure. The key idea is to use vocabularies with only monadic predicate and monadic function symbols -- so called singulary logic [Church]. Our proof is effective and syntactic, not relying on games or other semantic characterizations. Linear-time computability of first-order queries becomes a direct corollary of this result. Included will be a discussion of why these data structures are the appropriate models for physically realizable databases.

[Church, A.] Introduction to Mathematical Logic, Princeton University Press, 1956.

Related Links

Presentation

[ppt ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧