Sixteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2001)

Paper: A Model-Theoretic Approach to Regular String Relations (at LICS 2001)

Authors: Michael Benedikt Leonid Libkin Thomas Schwentick 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.


    author = 	 {Michael Benedikt and Leonid Libkin and Thomas Schwentick and Luc Segoufin},
    title = 	 {A Model-Theoretic Approach to Regular String Relations},
    booktitle =  {Proceedings of the Sixteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2001},
    year =	 2001,
    editor =	 {Joseph Halpern},
    month =	 {June}, 
    pages =      {431--},
    location =   {Boston, MA, USA}, 
    publisher =	 {IEEE Computer Society Press}