@ARTICLE{2005BGLS-AMAI,
  author = {Veronica Biazzo and Angelo Gilio and Thomas Lukasiewicz and Giuseppe
	Sanfilippo},
  title = {Probabilistic logic under coherence: complexity and algorithms.},
  journal = {Ann. Math. Artif. Intell.},
  year = {2005},
  volume = {45},
  pages = {35-81},
  number = {1-2},
  note = {ISSN 1012-2443},
  abstract = {In previous work [V. Biazzo, A. Gilio, T. Lukasiewicz and G. Sanfilippo,
	Probabilistic logic under coherence, model-theoretic probabilistic
	logic, and default reasoning in System P, Journal of Applied Non-Classical
	Logics 12(2) (2002) 189–213.], we have explored the relationship
	between probabilistic reasoning under coherence and model-theoretic
	probabilistic reasoning. In particular, we have shown that the notions
	of g-coherence and of g-coherent entailment in probabilistic reasoning
	under coherence can be expressed by combining notions in model-theoretic
	probabilistic reasoning with concepts from default reasoning. In
	this paper, we continue this line of research. Based on the above
	semantic results, we draw a precise picture of the computational
	complexity of probabilistic reasoning under coherence. Moreover,
	we introduce transformations for probabilistic reasoning under coherence,
	which reduce an instance of deciding g-coherence or of computing
	tight intervals under g-coherent entailment to a smaller problem
	instance, and which can be done very efficiently. Furthermore, we
	present new algorithms for deciding g-coherence and for computing
	tight intervals under g-coherent entailment, which reformulate previous
	algorithms using terminology from default reasoning. They are based
	on reductions to standard problems in model-theoretic probabilistic
	reasoning, which in turn can be reduced to linear optimization problems.
	Hence, efficient techniques for model-theoretic probabilistic reasoning
	can immediately be applied for probabilistic reasoning under coherence
	(for example, column generation techniques). We describe several
	such techniques, which transform problem instances in model-theoretic
	probabilistic reasoning into smaller problem instances. We also describe
	a technique for obtaining a reduced set of variables for the associated
	linear optimization problems in the conjunctive case, and give new
	characterizations of this reduced set as a set of non-decomposable
	variables, and using the concept of random gain.},
  doi = {10.1007/s10472-005-9005-y},
  issn = {1012-2443},
  mrclass = {68T37 (03B48)},
  mrnumber = {2220432 (2007a:68065)},
  scopus = {{2-s2.0-32544435240}},
  url = {http://dx.doi.org/10.1007/s10472-005-9005-y},
  wos = {{WOS:000235267600003}}
}