2 Search Results for "Ranise, Silvio"


Document
Rewriting-based Quantifier-free Interpolation for a Theory of Arrays

Authors: Roberto Bruttomesso, Silvio Ghilardi, and Silvio Ranise

Published in: LIPIcs, Volume 10, 22nd International Conference on Rewriting Techniques and Applications (RTA'11) (2011)


Abstract
The use of interpolants in model checking is becoming an enabling technology to allow fast and robust verification of hardware and software. The application of encodings based on the theory of arrays, however, is limited by the impossibility of deriving quantifier-free interpolants in general. In this paper, we show that, with a minor extension to the theory of arrays, it is possible to obtain quantifier-free interpolants. We prove this by designing an interpolating procedure, based on solving equations between array updates. Rewriting techniques are used in the key steps of the solver and its proof of correctness. To the best of our knowledge, this is the first successful attempt of computing quantifier-free interpolants for a theory of arrays.

Cite as

Roberto Bruttomesso, Silvio Ghilardi, and Silvio Ranise. Rewriting-based Quantifier-free Interpolation for a Theory of Arrays. In 22nd International Conference on Rewriting Techniques and Applications (RTA'11). Leibniz International Proceedings in Informatics (LIPIcs), Volume 10, pp. 171-186, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{bruttomesso_et_al:LIPIcs.RTA.2011.171,
  author =	{Bruttomesso, Roberto and Ghilardi, Silvio and Ranise, Silvio},
  title =	{{Rewriting-based Quantifier-free Interpolation for a Theory of Arrays}},
  booktitle =	{22nd International Conference on Rewriting Techniques and Applications (RTA'11)},
  pages =	{171--186},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-30-9},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{10},
  editor =	{Schmidt-Schauss, Manfred},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.RTA.2011.171},
  URN =		{urn:nbn:de:0030-drops-31155},
  doi =		{10.4230/LIPIcs.RTA.2011.171},
  annote =	{Keywords: rewriting, interpolation, arrays, model-checking}
}
Document
From Non-Disjoint Combination to Satisfiability and Model-Checking of Infinite State Systems

Authors: Silvio Ghilardi, Silvio Ranise, Enrica Nicolini, and Daniele Zucchelli

Published in: Dagstuhl Seminar Proceedings, Volume 7401, Deduction and Decision Procedures (2007)


Abstract
In the first part of our contribution, we review recent results on combined constraint satisfiability for first order theories in the non-disjoint signatures case: this is done mainly in view of the applications to temporal satisfiability and model-checking covered by the second part of our talk, but we also illustrate in more detail some case-study where non-disjoint combination arises. The first case deals with extensions of the theory of arrays where indexes are endowed with a Presburger arithmetic structure and a length expressing `dimension' is added; the second case deals with the algebraic counterparts of fusion in modal logics. We then recall the basic features of the Nelson-Oppen method and investigate sufficient conditions for it to be complete and terminating in the non-disjoint signatures case: for completeness we rely on a model-theoretic $T_0$-compatibility condition (generalizing stable infiniteness) and for termination we impose a noetherianity requirement on positive constraints chains. We finally supply examples of theories matching these combinability hypotheses. In the second part of our contribution, we develop a framework for integrating first-order logic (FOL) and discrete Linear time Temporal Logic (LTL). Manna and Pnueli have extensively shown how a mixture of FOL and LTL is sufficient to precisely state verification problems for the class of reactive systems: theories in FOL model the (possibly infinite) data structures used by a reactive system while LTL specifies its (dynamic) behavior. Our framework for the integration is the following: we fix a theory $T$ in a first-order signature $Sigma$ and consider as a temporal model a sequence $cM_1, cM_2, dots$ of standard (first-order) models of $T$ and assume such models to share the same carrier (or, equivalently, the domain of the temporal model to be `constant'). Following Plaisted, we consider symbols from a subsignature $Sigma_r$ of $Sigma$ to be emph{rigid}, i.e. in a temporal model $cM_1, cM_2, dots$, the $Sigma_r$-restrictions of the $cM_i$'s must coincide. The symbols in $Sigmasetminus Sigma_r$ are called `flexible' and their interpretation is allowed to change over time (free variables are similarly divided into `rigid' and `flexible'). For model-checking, the emph{initial states} and the emph{transition relation} are represented by first-order formulae, whose role is that of (non-deterministically) restricting the temporal evolution of the model. In the quantifier-free case, we obtain sufficient conditions for %undecidability and decidability for both satisfiability and model-checking of safety properties emph{by lifting combination methods} for emph{non-disjoint} theories in FOL: noetherianity and $T_0$-compatibility (where $T_0$ is the theory axiomatizing the rigid subtheory) gives decidability of satisfiability, whereas $T_0$-compatibility and local finiteness give safety model-checking decidability. The proofs of these decidability results suggest how decision procedures for the constraint satisfiability problem of theories in FOL and algorithms for checking the satisfiability of propositional LTL formulae can be integrated. This paves the way to employ efficient Satisfiability Modulo Theories solvers in the model-checking of infinite state systems. We illustrate our techniques on some examples and discuss further work in the area.

Cite as

Silvio Ghilardi, Silvio Ranise, Enrica Nicolini, and Daniele Zucchelli. From Non-Disjoint Combination to Satisfiability and Model-Checking of Infinite State Systems. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{ghilardi_et_al:DagSemProc.07401.4,
  author =	{Ghilardi, Silvio and Ranise, Silvio and Nicolini, Enrica and Zucchelli, Daniele},
  title =	{{From Non-Disjoint Combination to Satisfiability and Model-Checking of Infinite State Systems}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7401},
  editor =	{Franz Baader and Byron Cook and J\"{u}rgen Giesl and Robert Nieuwenhuis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.4},
  URN =		{urn:nbn:de:0030-drops-12479},
  doi =		{10.4230/DagSemProc.07401.4},
  annote =	{Keywords: Non disjoint combination, linear temporal logic, model checking}
}
  • Refine by Author
  • 2 Ghilardi, Silvio
  • 2 Ranise, Silvio
  • 1 Bruttomesso, Roberto
  • 1 Nicolini, Enrica
  • 1 Zucchelli, Daniele

  • Refine by Classification

  • Refine by Keyword
  • 1 Non disjoint combination
  • 1 arrays
  • 1 interpolation
  • 1 linear temporal logic
  • 1 model checking
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2007
  • 1 2011

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail