Characterization Results for d-Horn Formulas

C. Areces, V. Becher, and S. Ferro. Characterization Results for d-Horn Formulas. In Proceedings of ITALLC'98. Information Theoretic Approaches to Logic, Language and Computation, Hsi-Tow, Taiwan, 1998.

Download

[pdf] 

Abstract

We provide two di erent model theoretic characterizations of a new fragment of first-order logic which we call d-Horn formulas. This fragment is dual to the well know Horn fragment and have the same complexity for provability. The method used in the characterization (syntactic translation functions between formulas which are mimicked by translation functions between models) might be applied to characterize other first-order restrictions.

BibTeX

@InProceedings{Areces1998a,
  author =       "C. Areces and V. Becher and S. Ferro",
  booktitle =    "Proceedings of ITALLC'98. Information Theoretic
                 Approaches to Logic, Language and Computation",
  title =        "Characterization Results for d-{H}orn Formulas",
  year =         "1998",
  abstract =     "We provide two di erent model theoretic
                 characterizations of a new fragment of first-order
                 logic which we call d-Horn formulas. This fragment is
                 dual to the well know Horn fragment and have the same
                 complexity for provability. The method used in the
                 characterization (syntactic translation functions
                 between formulas which are mimicked by translation
                 functions between models) might be applied to
                 characterize other first-order restrictions.",
  address =      "Hsi-Tow, Taiwan",
}