Volume

Dagstuhl Seminar Proceedings, Volume 7401

Publication Details

  • published at: 2007-11-29
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.07401.1
07401 Abstracts Collection – Deduction and Decision Procedures

Authors: Franz Baader, Byron Cook, Jürgen Giesl, and Robert Nieuwenhuis

Abstract
From 01.10. to 05.10.2007, the Dagstuhl Seminar 07401 ``Deduction and Decision Procedures'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper.
Cite as

Franz Baader, Byron Cook, Jürgen Giesl, and Robert Nieuwenhuis. 07401 Abstracts Collection – Deduction and Decision Procedures. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{baader_et_al:DagSemProc.07401.1,
  author =	{Baader, Franz and Cook, Byron and Giesl, J\"{u}rgen and Nieuwenhuis, Robert},
  title =	{{07401 Abstracts Collection – Deduction and Decision Procedures}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--20},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.1},
  URN =		{urn:nbn:de:0030-drops-12521},
  doi =		{10.4230/DagSemProc.07401.1},
  annote =	{Keywords: Decision Procedures, Deduction, Boolean Satisfiability, First-Order Logic, Integer Arithmetic, Combination of Theories, Satisfiability Modulo Theories Rewrite Systems, Formal Verification, Model Finding}
}
Document
DOI: 10.4230/DagSemProc.07401.2
07401 Executive Summary – Deduction and Decision Procedures

Authors: Franz Baader, Byron Cook, Jürgen Giesl, and Robert Nieuwenhuis

Abstract
Formal logic provides a mathematical foundation for many areas of computer science. Significant progress has been made in the challenge of making computers perform non-trivial logical reasoning. be it fully automatic, or in interaction with humans. In the last years it has become more and more evident that theory-specific reasoners, and in particular decision procedures, are extremely important in many applications of such deduction tools. General-purpose reasoning methods such as resolution or paramodulation alone are not efficient enough to handle the needs of real-world applications. % For this reason, the focus of this seminar was on decision procedures, their integration into general-purpose theorem provers, and the application of the integrated tools in computer science.
Cite as

Franz Baader, Byron Cook, Jürgen Giesl, and Robert Nieuwenhuis. 07401 Executive Summary – Deduction and Decision Procedures. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{baader_et_al:DagSemProc.07401.2,
  author =	{Baader, Franz and Cook, Byron and Giesl, J\"{u}rgen and Nieuwenhuis, Robert},
  title =	{{07401 Executive Summary – Deduction and Decision Procedures}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--3},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.2},
  URN =		{urn:nbn:de:0030-drops-12515},
  doi =		{10.4230/DagSemProc.07401.2},
  annote =	{Keywords: Formal Logic, Deduction, Artificial Intelligence}
}
Document
DOI: 10.4230/DagSemProc.07401.3
Decision Procedures for Loop Detection

Authors: René Thiemann, Jürgen Giesl, and Peter Schneider-Kamp

Abstract
The dependency pair technique is a powerful modular method for automated termination proofs of term rewrite systems. We first show that dependency pairs are also suitable for disproving termination: loops can be detected more easily. In a second step we analyze how to disprove innermost termination. Here, we present a novel procedure to decide whether a given loop is an innermost loop. All results have been implemented in the termination prover AProVE.
Cite as

René Thiemann, Jürgen Giesl, and Peter Schneider-Kamp. Decision Procedures for Loop Detection. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{thiemann_et_al:DagSemProc.07401.3,
  author =	{Thiemann, Ren\'{e} and Giesl, J\"{u}rgen and Schneider-Kamp, Peter},
  title =	{{Decision Procedures for Loop Detection}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--17},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.3},
  URN =		{urn:nbn:de:0030-drops-12469},
  doi =		{10.4230/DagSemProc.07401.3},
  annote =	{Keywords: Non-Termination, Decision Procedures, Term Rewriting, Dependency Pairs}
}
Document
DOI: 10.4230/DagSemProc.07401.4
From Non-Disjoint Combination to Satisfiability and Model-Checking of Infinite State Systems

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

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.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}
}
Document
DOI: 10.4230/DagSemProc.07401.5
Implementing RPO and POLO using SAT

Authors: Peter Schneider-Kamp, Carsten Fuhs, René Thiemann, Jürgen Giesl, Elena Annov, Michael Codish, Aart Middeldorp, and Harald Zankl

Abstract
Well-founded orderings are the most basic, but also most important ingredient to virtually all termination analyses. The recursive path order with status (RPO) and polynomial interpretations (POLO) are the two classes that are the most popular in the termination analysis of term rewrite systems. Numerous fully automated search algorithms for these classes have therefore been devised and implemented in termination tools. Unfortunately, the performance of these algorithms on all but the smallest termination problems has been lacking. E.g., recently developed transformations from programming languages like Haskell or Prolog allow to apply termination tools for term rewrite systems to real programming languages. The results of the transformations are often of non-trivial size, though, and cannot be handled efficiently by the existing algorithms. The need for more efficient search algorithms has triggered research in reducing these search problems into decision problems for which more efficient algorithms already exist. Here, we introduce an encoding of RPO and POLO to the satisfiability of propositional logic (SAT). We implemented these encodings in our termination tool AProVE. Extensive experiments have shown that one can obtain speedups in orders of magnitude by this encoding and the application of modern SAT solvers. The talk is based on joint work with Elena Annov, Mike Codish, Carsten Fuhs, Jürgen Giesl, Aart Middeldorp, René Thiemann, and Harald Zankl.
Cite as

Peter Schneider-Kamp, Carsten Fuhs, René Thiemann, Jürgen Giesl, Elena Annov, Michael Codish, Aart Middeldorp, and Harald Zankl. Implementing RPO and POLO using SAT. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{schneiderkamp_et_al:DagSemProc.07401.5,
  author =	{Schneider-Kamp, Peter and Fuhs, Carsten and Thiemann, Ren\'{e} and Giesl, J\"{u}rgen and Annov, Elena and Codish, Michael and Middeldorp, Aart and Zankl, Harald},
  title =	{{Implementing RPO and POLO using SAT}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--10},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.5},
  URN =		{urn:nbn:de:0030-drops-12491},
  doi =		{10.4230/DagSemProc.07401.5},
  annote =	{Keywords: Termination, SAT, recursive path order, polynomial interpretation}
}
Document
DOI: 10.4230/DagSemProc.07401.6
Local Theory Extensions, Hierarchical Reasoning and Applications to Verification

Authors: Viorica Sofronie-Stokkermans, Carsten Ihlemann, and Swen Jacobs

Abstract
Many problems occurring in verification can be reduced to proving the satisfiability of conjunctions of literals in a background theory. This can be a concrete theory (e.g. the theory of real or rational numbers), the extension of a theory with additional functions (free, monotone, or recursively defined) or a combination of theories. It is therefore very important to have efficient procedures for checking the satisfiability of conjunctions of ground literals in such theories. We present some new results on hierarchical and modular reasoning in complex theories, as well as several examples of application domains in which efficient reasoning is possible. We show, in particular, that various phenomena analyzed in the verification literature can be explained in a unified way using the notion of local theory extension.
Cite as

Viorica Sofronie-Stokkermans, Carsten Ihlemann, and Swen Jacobs. Local Theory Extensions, Hierarchical Reasoning and Applications to Verification. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{sofroniestokkermans_et_al:DagSemProc.07401.6,
  author =	{Sofronie-Stokkermans, Viorica and Ihlemann, Carsten and Jacobs, Swen},
  title =	{{Local Theory Extensions, Hierarchical Reasoning and Applications to Verification}},
  booktitle =	{Deduction and Decision Procedures},
  pages =	{1--22},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.6},
  URN =		{urn:nbn:de:0030-drops-12507},
  doi =		{10.4230/DagSemProc.07401.6},
  annote =	{Keywords: Automated reasoning, Combinations of decision procedures, Verification}
}
Document
DOI: 10.4230/DagSemProc.07401.7
Termination of Programs using Term Rewriting and SAT Solving

Authors: Jürgen Giesl, Peter Schneider-Kamp, René Thiemann, Stephan Swiderski, Manh Thang Nguyen, Daniel De Schreye, and Alexander Serebrenik

Abstract
There are many powerful techniques for automated termination analysis of term rewrite systems (TRSs). However, up to now they have hardly been used for real programming languages. In this talk, we describe recent results which permit the application of existing techniques from term rewriting in order to prove termination of programs. We discuss two possible approaches: 1. One could translate programs into TRSs and then use existing tools to verify termination of the resulting TRSs. 2. One could adapt TRS-techniques to the respective programming languages in order to analyze programs directly. We present such approaches for the functional language Haskell and the logic language Prolog. Our results have been implemented in the termination provers AProVE and Polytool. In order to handle termination problems resulting from real programs, these provers had to be coupled with modern SAT solvers, since the automation of the TRS-termination techniques had to improve significantly. Our resulting termination analyzers are currently the most powerful ones for Haskell and Prolog.
Cite as

Jürgen Giesl, Peter Schneider-Kamp, René Thiemann, Stephan Swiderski, Manh Thang Nguyen, Daniel De Schreye, and Alexander Serebrenik. Termination of Programs using Term Rewriting and SAT Solving. In Deduction and Decision Procedures. Dagstuhl Seminar Proceedings, Volume 7401, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{giesl_et_al:DagSemProc.07401.7,
  author =	{Giesl, J\"{u}rgen and Schneider-Kamp, Peter and Thiemann, Ren\'{e} and Swiderski, Stephan and Nguyen, Manh Thang and De Schreye, Daniel and Serebrenik, Alexander},
  title =	{{Termination of Programs using Term Rewriting and SAT Solving}},
  booktitle =	{Deduction and Decision Procedures},
  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.dagstuhl.de/entities/document/10.4230/DagSemProc.07401.7},
  URN =		{urn:nbn:de:0030-drops-12481},
  doi =		{10.4230/DagSemProc.07401.7},
  annote =	{Keywords: Termination, Term Rewriting, Haskell, Prolog, SAT Solving}
}

Filters

  • Authors
  • A
  • Annov, Elena
  • B
  • Baader, Franz
  • C
  • Codish, Michael
  • Cook, Byron
  • D
  • De Schreye, Daniel
  • F
  • Fuhs, Carsten
  • G
  • Ghilardi, Silvio
  • Giesl, Jürgen
  • I
  • Ihlemann, Carsten
  • J
  • Jacobs, Swen
  • M
  • Middeldorp, Aart
  • N
  • Nguyen, Manh Thang
  • Nicolini, Enrica
  • Nieuwenhuis, Robert
  • R
  • Ranise, Silvio
  • S
  • Schneider-Kamp, Peter
  • Serebrenik, Alexander
  • Sofronie-Stokkermans, Viorica
  • Swiderski, Stephan
  • T
  • Thiemann, René
  • Z
  • Zankl, Harald
  • Zucchelli, Daniele

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact