Bounded Model Checking of Pointer Programs Revisited
  Bounded model checking of pointer programs is a debugging technique for programs that manipulate dynamically allocated pointer structures on the heap. It is based on the following four observations. First, error conditions like dereference of a dangling pointer, are expressible in a~fragment of first-order logic with two-variables. Second, the fragment is closed under weakest preconditions wrt. finite paths. Third, data structures like trees, lists etc. are expressible by inductive predicates defined in a fragment of Datalog. Finally, the combination of the two fragments of the two-variable logic and Datalog is decidable.   In this paper we improve this technique by extending the expressivity of the underlying logics. In a~sequence of examples we demonstrate that the new logic is capable of modeling more sophisticated data structures with more complex dependencies on heaps and more complex analyses. 
Witold Charatonik and Piotr Witkowski
cs.LO cs.PL