ACM DL

Computational Logic (TOCL)

Menu

Search Issue
enter search term and/or author name

Archive


ACM Transactions on Computational Logic (TOCL), Volume 3 Issue 4, October 2002

Deciding and axiomatizing weak ST bisimulation for a process algebra with recursion and action refinement
Mario Bravetti, Roberto Gorrieri
Pages: 465-520
DOI: 10.1145/566385.566386
Due to the complex nature of bisimulation equivalences that express some form of history dependence, it turned out to be problematic to decide them over nontrivial classes of recursive systems. Moreover, to the best of our knowledge, the problem of...

Polynomial-time computation via local inference relations
Robert Givan, David Mcallester
Pages: 521-541
DOI: 10.1145/566385.566387
We consider the concept of a local set of inference rules. A local rule set can be automatically transformed into a rule set for which bottom-up evaluation terminates in polynomial time. The local-rule-set transformation gives polynomial-time...

Revisiting quantification in autoepistemic logic
Michael Kaminski, Guy Rey
Pages: 542-561
DOI: 10.1145/566385.566388
In this article, we introduce first-order autoepistemic logic. Our definition is semantical and is based on the intuition similar to that lying behind the definition of first-order default logic. Thus, our definition of first-order...

Typed interpretations of extensible objects
Viviana Bono, Michele Bugliesi, Silvia Crafa
Pages: 562-603
DOI: 10.1145/566385.566389
Finding typed encodings of object-oriented into procedural or functional programming sheds light on the theoretical foundations of object-oriented languages and their specific typing constructs and techniques. This article describes a type preserving...

Boolean satisfiability with transitivity constraints
Randal E. Bryant, Miroslav N. Velev
Pages: 604-627
DOI: 10.1145/566385.566390
We consider a variant of the Boolean satisfiability problem where a subset ϵ of the propositional variables appearing in formula Fsat encode a symmetric, transitive, binary relation over N elements. Each of these...