We consider a technique for liveness and termination proofs that reduces temporal proofs to verification conditions in uninterpreted first-order logic based on a suitable notion of a fair abstract lasso. It was previously shown that temporal prophecy makes the technique more powerful, essentially empowering it to prove termination of nested loops. In this paper we show that temporal prophecy is even more powerful than previously demonstrated: it can even prove termination of the Ackermann function, which is not primitive recursive, and essentially represents “infinitely-many” nested loops.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Power of Temporal Prophecy

  • Jochen Hoenicke,
  • Oded Padon,
  • Sharon Shoham

摘要

We consider a technique for liveness and termination proofs that reduces temporal proofs to verification conditions in uninterpreted first-order logic based on a suitable notion of a fair abstract lasso. It was previously shown that temporal prophecy makes the technique more powerful, essentially empowering it to prove termination of nested loops. In this paper we show that temporal prophecy is even more powerful than previously demonstrated: it can even prove termination of the Ackermann function, which is not primitive recursive, and essentially represents “infinitely-many” nested loops.