Characterization Results for d-Horn Formulas

Areces, C., Becher, V., and Ferro, S.. Characterization Results for d-Horn Formulas. In Cavedon, L., Blackburn, P., Braisby, N., and Shimojima, A., editors, Logic, Language and Computation, pp. 49–66, CSLI Publications, 2000. Extended version of ``Characterization Results for d-Horn Formulas'' (Areces, Becher and Ferro).

Download: [pdf] 

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 \shortcitehens: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.

BibTeX: (download)

@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.},
}

Generated by bib2html.pl (written by Patrick Riley) on Sun Oct 02, 2016 17:05:49