@INCOLLECTION{arec:char00,
author = {Areces, C. and Becher, V. and Ferro, S.},
title = {Characterization Results for d-{H}orn Formulas},
booktitle = {Logic, Language and Computation},
publisher = {CSLI Publications},
year = {2000},
editor = {Cavedon, L. and Blackburn, P. and Braisby, N. and Shimojima, A.},
volume = {3},
pages = {49--66},
note = {Extended version of ``Characterization Results for d-{H}orn Formulas''
(Areces, Becher and Ferro).},
abstract = {We provide two different model theoretic characterizations of a fragment
of first-order logic which we call d-Horn formulas. This fragment
is dual to the well known Horn fragment and has the same complexity
for proving unsatisfiability. 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. This paper is related to the work
of Henschen and Wos \shortcite{hens:unit74}, but we study semantic
translation together with syntactic renaming functions. We comment
shortly on a number of applications of d-Horn formulas, one of which
is the characterization of Context Free Grammars through a Horn $\cup$
d-Horn first-order theory.},
}