#### ACM Transactions on Computational Logic (TOCL), Volume 2 Issue 3, July 2001

**Probabilistic logic programming with conditional constraints**

Thomas Lukasiewicz

Pages: 289-339

DOI: 10.1145/377978.377983

We introduce a new approach to probabilistic logic programming in which probabilities are defined over a set of possible worlds. More precisely, classical program clauses are extended by a subinterval of [0,1] that describes a range for the...

**Proof-complexity results for nonmonotonic reasoning**

Uwe Egly, Hans Tompits

Pages: 340-387

DOI: 10.1145/377978.377987

It is well-known that almost all nonmonotonic formalisms have a higher worst-case complexity than classical reasoning. In some sense, this observation denies one of the original motivations of nonmonotonic systems, which was the expectation taht...

**Parametric temporal logic for “model measuring”**

Rajeev Alur, Kousha Etessami, Salvatore La Torre, Doron Peled

Pages: 388-407

DOI: 10.1145/377978.377990

We extend the standard model checking paradigm of linear temporal logic, LTL, to a “model measuring” paradigm where one can obtain more quantitative information beyond a “Yes/No” answer. For this purpose, we define a...

**Weak alternating automata are not that weak**

Orna Kupferman, Moshe Y. Vardi

Pages: 408-429

DOI: 10.1145/377978.377993

Automata on infinite words are used for specification and verification of nonterminating programs. Different types of automata induce different levels of expressive power, of succinctness, and of complexity. Alternating automata...