Politeness and Stable Infiniteness: Stronger Together
Open Access
- 5 July 2021
- book chapter
- Published by Springer Nature
- p. 148-165
Abstract
We make two contributions to the study of polite combination in satisfiability modulo theories. The first is a separation between politeness and strong politeness, by presenting a polite theory that is not strongly polite. This result shows that proving strong politeness (which is often harder than proving politeness) is sometimes needed in order to use polite combination. The second contribution is an optimization to the polite combination method, obtained by borrowing from the Nelson-Oppen method. The Nelson-Oppen method is based on guessing arrangements over shared variables. In contrast, polite combination requires an arrangement overallvariables of the shared sorts. We show that when using polite combination, if the other theory is stably infinite with respect to a shared sort, only the shared variables of that sort need be considered in arrangements, as in the Nelson-Oppen method. The time required to reason about arrangements is exponential in the worst case, so reducing the number of variables considered has the potential to improve performance significantly. We show preliminary evidence for this by demonstrating a speed-up on a smart contract verification benchmark.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Satisfiability Modulo Theories2018
- Many-Sorted Equivalence of Shiny and Strongly Polite TheoriesJournal of Automated Reasoning, 2017
- Revisiting the Equivalence of Shininess and Politeness2013
- CVC42011
- Polite Theories Revisited2010
- Combinations of Theories for Decidable Fragments of First-Order Logic2009
- Combined Satisfiability Modulo Parametric Theories2007
- An Abstract Decision Procedure for a Theory of Inductive Data TypesJournal on Satisfiability, Boolean Modeling and Computation, 2007
- Introduction2001
- Simplification by Cooperating Decision ProceduresACM Transactions on Programming Languages and Systems, 1979