A Model-Theoretic Approach to Regular String Relations
paper (LICS 2001)
Michael Benedikt, Leonid Libkin, Thomas Schwentick and Luc Segoufin
We study algebras of definable string relations
-- classes of regular n-ary relations that
arise as the definable sets within a
model whose carrier is the set of all strings.
We show that the largest such algebra -- the collection
of regular relations -- has some quite undesirable
computational and model-theoretic properties. In contrast,
we exhibit several definable relation algebras that
have much tamer behavior: for example, they admit quantifier
elimination, and have finite VC dimension.
We show that
the properties of a definable relation algebra are not
at all determined by the one-dimensional definable sets.
We give models whose definable sets are all star-free, but
whose binary relations are quite complex, as well as
models whose definable sets include all regular sets, but which
are much more restricted and tractable than the full algebra
of regular relations.
Back to Luc Segoufin's home page.