Paper: Approximate Satisfiability and Equivalence (at LICS 2006)

Authors: Eldar Fischer Frédéric Magniez Michel de Rougemont

Abstract

Inspired by Property Testing, we relax the classical satisfiability U |= F between a finite structure U of a class K and a formula F, to a notion of \varessilon-satisfiability U |=\varepsilon F, and the classical equivalence F_1 \equiv F_2 between two formulas F_1 and F_2, to \varepsilon-equivalence F1 \equiv_\varepsilon F2 for \varepsilon > 0. We consider the class of strings and trees with the edit distance with moves, and show that these approximate notions can be efficiently decided. We use a statistical embedding of words (resp. trees) into l_1, which generalizes the original Parikh mapping, obtained by sampling O(f(\epsilon)) finite samples of the words (resp. trees). We give a tester for equality and membership in any regular language, in time independent of the size of the structure. Using our geometrical embedding, we can also test the equivalence between two regular properties on words, defined by Monadic Second Order formulas. Our equivalence tester has polynomial time complexity in the size of the automaton (or regular expression), for a fixed varepisolon, whereas the exact version of the equivalence problem is PSPACE-complete. Last, we extend the geometric embedding, and hence the tester algorithms, to infinite regular languages and to context-free languages. For context-free languages, the equivalence tester has an exponential time complexity, whereas the exact version is undecidable.

BibTeX

  @InProceedings{FischerMagniezdeRou-ApproximateSatisfia,
    author = 	 {Eldar Fischer and Frédéric Magniez and Michel de Rougemont},
    title = 	 {Approximate Satisfiability and Equivalence},
    booktitle =  {Proceedings of the Twenty-First Annual IEEE Symposium on Logic in Computer Science (LICS 2006)},
    year =	 {2006},
    month =	 {August}, 
    pages =      {421--430},
    location =   {Seattle, Washington, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }