A Decision Procedure for (Co)datatypes in SMT Solvers

by Andrew Reynolds, Jasmin Christian Blanchette
Abstract:
We present a decision procedure that combines reasoning about datatypes and codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies observationally equal codatatype values, including cyclic values. The procedure decides universal problems and is composable via the Nelson-Oppen method. It has been implemented in CVC4, a state-of-the-art SMT solver. An evaluation based on problems generated from formalizations developed with Isabelle demonstrates the potential of the procedure.
Reference:
A Decision Procedure for (Co)datatypes in SMT Solvers (Andrew Reynolds, Jasmin Christian Blanchette), In J. Autom. Reasoning, volume 58, 2017.
Bibtex Entry:
@article{DBLP:journals/jar/ReynoldsB17,
  author    = {Andrew Reynolds and
               Jasmin Christian Blanchette},
  title     = {A Decision Procedure for (Co)datatypes in {SMT} Solvers},
  journal   = {J. Autom. Reasoning},
  volume    = {58},
  number    = {3},
  pages     = {341--362},
  year      = {2017},
  url       = {https://doi.org/10.1007/s10817-016-9372-6},
  doi       = {10.1007/s10817-016-9372-6},
  timestamp = {Sat, 20 May 2017 00:22:32 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jar/ReynoldsB17},
  bibsource = {dblp computer science bibliography, http://dblp.org},
  abstract  = "We present a decision procedure that combines reasoning about datatypes and
codatatypes. The dual of the acyclicity rule for datatypes is a uniqueness rule that identifies
observationally equal codatatype values, including cyclic values. The procedure decides universal
problems and is composable via the Nelson-Oppen method. It has been implemented
in CVC4, a state-of-the-art SMT solver. An evaluation based on problems generated from
formalizations developed with Isabelle demonstrates the potential of the procedure."
}

Fork me on GitHub