enter search term and/or author name
Deciding and axiomatizing weak ST bisimulation for a process algebra with recursion and action refinement
Mario Bravetti, Roberto Gorrieri
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
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
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
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
We consider a variant of the Boolean satisfiability problem where a subset ϵ of the propositional variables appearing in formula F