License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2013.303
URN: urn:nbn:de:0030-drops-40696
URL: https://drops.dagstuhl.de/opus/volltexte/2013/4069/
Go to the corresponding LIPIcs Volume Portal

Tushkanova, Elena ; Ringeissen, Christophe ; Giorgetti, Alain ; Kouchnarenko, Olga

Automatic Decidability: A Schematic Calculus for Theories with Counting Operators

pdf-format:
22.pdf (0.6 MB)

Abstract

Many verification problems can be reduced to a satisfiability problem
modulo theories. For building satisfiability procedures the rewriting-based approach uses a general calculus for equational reasoning named paramodulation. Schematic paramodulation, in turn, provides means to reason on the derivations computed by paramodulation. Until now, schematic paramodulation was only studied for standard paramodulation. We present a schematic paramodulation calculus modulo a fragment of arithmetics, namely the theory of Integer Offsets. This new schematic calculus is used to prove the decidability of the satisfiability problem for some theories equipped with counting operators. We illustrate our theoretical contribution on theories representing extensions of classical data structures, e.g., lists and records. An implementation within the rewriting-based Maude system constitutes a practical contribution. It enables automatic decidability proofs for theories of practical use.

BibTeX - Entry

@InProceedings{tushkanova_et_al:LIPIcs:2013:4069,
  author =	{Elena Tushkanova and Christophe  Ringeissen and Alain Giorgetti and Olga Kouchnarenko},
  title =	{{Automatic Decidability: A Schematic Calculus for Theories with Counting Operators}},
  booktitle =	{24th International Conference on Rewriting Techniques and Applications (RTA 2013)},
  pages =	{303--318},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-53-8},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{21},
  editor =	{Femke van Raamsdonk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4069},
  URN =		{urn:nbn:de:0030-drops-40696},
  doi =		{10.4230/LIPIcs.RTA.2013.303},
  annote =	{Keywords: decision procedures, superposition, schematic saturation}
}

Keywords: decision procedures, superposition, schematic saturation
Collection: 24th International Conference on Rewriting Techniques and Applications (RTA 2013)
Issue Date: 2013
Date of publication: 24.06.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI