Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2016) |
last year
(2015) |
two years ago
(2014) |
Notes URL
Action:
login to update
Options:
Goto entry point
Author, Editor
Author(s):
Sofronie-Stokkermans, Viorica
dblp
Editor(s):
Konev, Boris
Wolter, Frank
dblp
dblp
Not MPII Editor(s):
Konev, Boris
Wolter, Frank
BibTeX cite key*:
Sofronie-Stokkermans-frocos-07
Title, Booktitle
Title*:
Hierarchical and modular reasoning in complex theories: The case of local theory extensions
Booktitle*:
Frontiers of Combining Systems. 6th International Symposium FroCos 2007, Proceedings
Event, URLs
URL of the conference:
http://www.csc.liv.ac.uk/~frocos07/
URL for downloading the paper:
Event Address*:
Liverpool, UK
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
10 September 2007
Event End Date:
12 September 2007
Publisher
Name*:
Springer
URL:
http://www.springer-ny.com/
Address*:
New York
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4720
Number:
Month:
Pages:
47-71
Year*:
2007
VG Wort Pages:
41
ISBN/ISSN:
978-3-540-74620-1
Sequence Number:
DOI:
10.1007/978-3-540-74621-8_3
Note, Abstract, ©
Note:
Invited paper
(LaTeX) Abstract:
Many problems in computer science can be reduced to proving the satisfiability of conjunctions of literals w.r.t. a background theory. This theory 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 here give an overview of results on hierarchical and modular reasoning in complex theories. We show that for a special type of extensions of a base theory, which we call local, hierarchic reasoning is possible (i.e. proof tasks in the extension can be hierarchically reduced to proof tasks w.r.t. the base theory). Many theories important for computer science or mathematics fall into this class (typical examples are theories of data structures, theories of free or monotone functions, but also functions occurring in mathematical analysis).
In fact, it is often necessary to consider complex extensions, in which various types of functions or data structures need to be taken into account at the same time. We show how such local theory extensions can be identified and under which conditions locality is preserved when combining theories, and we investigate possibilities of efficient modular reasoning in such theory combinations.
We present several examples of application domains where such theories occur in a natural way. We show, in particular, that various phenomena analyzed in the verification literature can be explained in a unified way using the notion of locality.
Download
Access Level:
Public
Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Automation of Logic
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort
BibTeX Entry:
@INPROCEEDINGS
{
Sofronie-Stokkermans-frocos-07
,
AUTHOR = {Sofronie-Stokkermans, Viorica},
EDITOR = {Konev, Boris and Wolter, Frank},
TITLE = {Hierarchical and modular reasoning in complex theories: The case of local theory extensions},
BOOKTITLE = {Frontiers of Combining Systems. 6th International Symposium FroCos 2007, Proceedings},
PUBLISHER = {Springer},
YEAR = {2007},
VOLUME = {4720},
PAGES = {47--71},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Liverpool, UK},
ISBN = {978-3-540-74620-1},
DOI = {10.1007/978-3-540-74621-8_3},
NOTE = {Invited paper},
}
Entry last modified by Viorica Sofronie-Stokkermans, 02/28/2008
Edit History (please click the blue arrow to see the details)
Attachment Section