# The Year Before Last

Baumgartner, P., & Waldmann, U. (2019a). Hierarchic Superposition Revisited. Retrieved from http://arxiv.org/abs/1904.03776
(arXiv: 1904.03776)
Abstract
Many applications of automated deduction require reasoning in first-order logic modulo background theories, in particular some form of integer arithmetic. A major unsolved research challenge is to design theorem provers that are "reasonably complete" even in the presence of free function symbols ranging into a background theory sort. The hierarchic superposition calculus of Bachmair, Ganzinger, and Waldmann already supports such symbols, but, as we demonstrate, not optimally. This paper aims to rectify the situation by introducing a novel form of clause abstraction, a core component in the hierarchic superposition calculus for transforming clauses into a form needed for internal operation. We argue for the benefits of the resulting calculus and provide two new completeness results: one for the fragment where all background-sorted terms are ground and another one for a special case of linear (integer or rational) arithmetic as a background theory.
Export
BibTeX
@online{Baumgartner_arXIv1904.03776, TITLE = {Hierarchic Superposition Revisited}, AUTHOR = {Baumgartner, Peter and Waldmann, Uwe}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1904.03776}, EPRINT = {1904.03776}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Many applications of automated deduction require reasoning in first-order logic modulo background theories, in particular some form of integer arithmetic. A major unsolved research challenge is to design theorem provers that are "reasonably complete" even in the presence of free function symbols ranging into a background theory sort. The hierarchic superposition calculus of Bachmair, Ganzinger, and Waldmann already supports such symbols, but, as we demonstrate, not optimally. This paper aims to rectify the situation by introducing a novel form of clause abstraction, a core component in the hierarchic superposition calculus for transforming clauses into a form needed for internal operation. We argue for the benefits of the resulting calculus and provide two new completeness results: one for the fragment where all background-sorted terms are ground and another one for a special case of linear (integer or rational) arithmetic as a background theory.}, }
Endnote
%0 Report %A Baumgartner, Peter %A Waldmann, Uwe %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society %T Hierarchic Superposition Revisited : %G eng %U http://hdl.handle.net/21.11116/0000-0004-03C0-F %U http://arxiv.org/abs/1904.03776 %D 2019 %X Many applications of automated deduction require reasoning in first-order logic modulo background theories, in particular some form of integer arithmetic. A major unsolved research challenge is to design theorem provers that are "reasonably complete" even in the presence of free function symbols ranging into a background theory sort. The hierarchic superposition calculus of Bachmair, Ganzinger, and Waldmann already supports such symbols, but, as we demonstrate, not optimally. This paper aims to rectify the situation by introducing a novel form of clause abstraction, a core component in the hierarchic superposition calculus for transforming clauses into a form needed for internal operation. We argue for the benefits of the resulting calculus and provide two new completeness results: one for the fragment where all background-sorted terms are ground and another one for a special case of linear (integer or rational) arithmetic as a background theory. %K Computer Science, Logic in Computer Science, cs.LO
Baumgartner, P., & Waldmann, U. (2019b). Hierarchic Superposition Revisited. In Description Logic, Theory Combination, and All That. Berlin: Springer. doi:10.1007/978-3-030-22102-7_2
Export
BibTeX
@incollection{Baumgartner2019, TITLE = {Hierarchic Superposition Revisited}, AUTHOR = {Baumgartner, Peter and Waldmann, Uwe}, LANGUAGE = {eng}, ISBN = {978-3-030-22101-0}, DOI = {10.1007/978-3-030-22102-7_2}, PUBLISHER = {Springer}, ADDRESS = {Berlin}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Description Logic, Theory Combination, and All That}, EDITOR = {Lutz, Carsten and Sattler, Uli and Tinelli, Cesare and Turhan, Anni-Yasmin and Wolter, Frank}, PAGES = {15--56}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {11560}, }
Endnote
%0 Book Section %A Baumgartner, Peter %A Waldmann, Uwe %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society %T Hierarchic Superposition Revisited : %G eng %U http://hdl.handle.net/21.11116/0000-0004-03B5-C %R 10.1007/978-3-030-22102-7_2 %D 2019 %B Description Logic, Theory Combination, and All That %E Lutz, Carsten; Sattler, Uli; Tinelli, Cesare; Turhan, Anni-Yasmin; Wolter, Frank; Baader, Franz %P 15 - 56 %I Springer %C Berlin %@ 978-3-030-22101-0 %S Lecture Notes in Computer Science %N 11560
Bentkamp, A., Blanchette, J. C., Tourret, S., Vukmirović, P., & Waldmann, U. (2019). Superposition with Lambdas. In Automated Deduction -- CADE 27. Natal, Brazil: Springer. doi:10.1007/978-3-030-29436-6_4
Export
BibTeX
@inproceedings{Bentkamp_CADE2019, TITLE = {Superposition with Lambdas}, AUTHOR = {Bentkamp, Alexander and Blanchette, Jasmin Christian and Tourret, Sophie and Vukmirovi{\'c}, Petar and Waldmann, Uwe}, LANGUAGE = {eng}, ISSN = {0302-9743}, ISBN = {978-3-030-29435-9}, DOI = {10.1007/978-3-030-29436-6_4}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Automated Deduction -- CADE 27}, EDITOR = {Fontaine, Pascal}, PAGES = {55--73}, SERIES = {Lecture Notes in Artificial Intelligence}, VOLUME = {11716}, ADDRESS = {Natal, Brazil}, }
Endnote
%0 Conference Proceedings %A Bentkamp, Alexander %A Blanchette, Jasmin Christian %A Tourret, Sophie %A Vukmirovi&#263;, Petar %A Waldmann, Uwe %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society External Organizations Automation of Logic, MPI for Informatics, Max Planck Society %T Superposition with Lambdas : %G eng %U http://hdl.handle.net/21.11116/0000-0005-885C-B %R 10.1007/978-3-030-29436-6_4 %D 2019 %B 27th International Conference on Automated Deduction %Z date of event: 2019-08-27 - 2019-08-30 %C Natal, Brazil %B Automated Deduction -- CADE 27 %E Fontaine, Pascal %P 55 - 73 %I Springer %@ 978-3-030-29435-9 %B Lecture Notes in Artificial Intelligence %N 11716 %@ false
Bentkamp, A., Blanchette, J. C., & Klakow, D. (2019). A Formal Proof of the Expressiveness of Deep Learning. Journal of Automated Reasoning, 63(2). doi:10.1007/s10817-018-9481-5
Export
BibTeX
@article{Bentkamp2019, TITLE = {A Formal Proof of the Expressiveness of Deep Learning}, AUTHOR = {Bentkamp, Alexander and Blanchette, Jasmin Christian and Klakow, Dietrich}, LANGUAGE = {eng}, ISSN = {0168-7433}, DOI = {10.1007/s10817-018-9481-5}, PUBLISHER = {Springer}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, JOURNAL = {Journal of Automated Reasoning}, VOLUME = {63}, NUMBER = {2}, PAGES = {347--368}, }
Endnote
%0 Journal Article %A Bentkamp, Alexander %A Blanchette, Jasmin Christian %A Klakow, Dietrich %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T A Formal Proof of the Expressiveness of Deep Learning : %G eng %U http://hdl.handle.net/21.11116/0000-0004-7A8F-3 %R 10.1007/s10817-018-9481-5 %7 2019 %D 2019 %J Journal of Automated Reasoning %V 63 %N 2 %& 347 %P 347 - 368 %I Springer %C New York, NY %@ false
Blanchette, J. C. (2019). Formalizing the Metatheory of Logical Calculi and Automatic Provers in Isabelle/HOL (Invited Talk). In CPP’19, 8th ACM SIGPLAN International Conference on Certified Programs and Proofs. Cascais, Portugal: ACM. doi:10.1145/3293880.3294087
Export
BibTeX
@inproceedings{Blanchette_CPP2019, TITLE = {Formalizing the metatheory of logical calculi and automatic provers in {I}sabelle/{HOL} (invited talk)}, AUTHOR = {Blanchette, Jasmin Christian}, LANGUAGE = {eng}, ISBN = {978-1-4503-6222-1}, DOI = {10.1145/3293880.3294087}, PUBLISHER = {ACM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {CPP'19, 8th ACM SIGPLAN International Conference on Certified Programs and Proofs}, EDITOR = {Mahboubi, Assia and Myreen, Magnus O.}, PAGES = {1--13}, ADDRESS = {Cascais, Portugal}, }
Endnote
%0 Conference Proceedings %A Blanchette, Jasmin Christian %+ Automation of Logic, MPI for Informatics, Max Planck Society %T Formalizing the Metatheory of Logical Calculi and Automatic Provers in Isabelle/HOL (Invited Talk) : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E5A0-6 %R 10.1145/3293880.3294087 %D 2019 %B 8th ACM SIGPLAN International Conference on Certified Programs and Proofs %Z date of event: 2019-01-14 - 2019-01-15 %C Cascais, Portugal %B CPP'19 %E Mahboubi, Assia; Myreen, Magnus O. %P 1 - 13 %I ACM %@ 978-1-4503-6222-1
Blanchette, J. C., Gheri, L., Popescu, A., & Traytel, D. (2019). Bindings as Bounded Natural Functors. Proceedings of the ACM on Programming Languages (Proc. POPL 2019), 3. doi:10.1145/3290335
Export
BibTeX
@article{Blanchette_POPL2019, TITLE = {Bindings as Bounded Natural Functors}, AUTHOR = {Blanchette, Jasmin Christian and Gheri, Lorenzo and Popescu, Andrei and Traytel, Dmitriy}, LANGUAGE = {eng}, ISSN = {2475-1421}, DOI = {10.1145/3290335}, PUBLISHER = {ACM}, ADDRESS = {New York, NY}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {Proceedings of the ACM on Programming Languages (Proc. POPL)}, VOLUME = {3}, EID = {22}, BOOKTITLE = {46th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2019)}, }
Endnote
%0 Journal Article %A Blanchette, Jasmin Christian %A Gheri, Lorenzo %A Popescu, Andrei %A Traytel, Dmitriy %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Bindings as Bounded Natural Functors : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E59A-E %R 10.1145/3290335 %7 2019 %D 2019 %J Proceedings of the ACM on Programming Languages %O PACMPL %V 3 %Z sequence number: 22 %I ACM %C New York, NY %@ false %B 46th ACM SIGPLAN Symposium on Principles of Programming Languages %O POPL 2019 Sun 13 - Sat 19 January 2019 Cascais, Portugal
Bradford, R., Davenport, J. H., England, M., Errami, H., Gerdt, V., Grigoriev, D., … Weber, A. (2019). Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks. Retrieved from http://arxiv.org/abs/1902.04882
(arXiv: 1902.04882)
Abstract
We consider a problem from biological network analysis of determining regions in a parameter space over which there are multiple steady states for positive real values of variables and parameters. We describe multiple approaches to address the problem using tools from Symbolic Computation. We describe how progress was made to achieve semi-algebraic descriptions of the multistationarity regions of parameter space, and compare symbolic results to numerical methods. The biological networks studied are models of the mitogen-activated protein kinases (MAPK) network which has already consumed considerable effort using special insights into its structure of corresponding models. Our main example is a model with 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment. The model also imposes positivity conditions on all variables and parameters. We apply combinations of symbolic computation methods designed for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition, as well as a simplification technique adapted from Gaussian elimination and graph theory. We are able to determine multistationarity of our main example over a 2-dimensional parameter space. We also study a second MAPK model and a symbolic grid sampling technique which can locate such regions in 3-dimensional parameter space.
Export
BibTeX
@online{Bradford_arXiv1902.04882, TITLE = {Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks}, AUTHOR = {Bradford, Russell and Davenport, James H. and England, Matthew and Errami, Hassan and Gerdt, Vladimir and Grigoriev, Dima and Hoyt, Charles and Ko{\v s}ta, Marek and Radulescu, Ovidiu and Sturm, Thomas and Weber, Andreas}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1902.04882}, EPRINT = {1902.04882}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider a problem from biological network analysis of determining regions in a parameter space over which there are multiple steady states for positive real values of variables and parameters. We describe multiple approaches to address the problem using tools from Symbolic Computation. We describe how progress was made to achieve semi-algebraic descriptions of the multistationarity regions of parameter space, and compare symbolic results to numerical methods. The biological networks studied are models of the mitogen-activated protein kinases (MAPK) network which has already consumed considerable effort using special insights into its structure of corresponding models. Our main example is a model with 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment. The model also imposes positivity conditions on all variables and parameters. We apply combinations of symbolic computation methods designed for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition, as well as a simplification technique adapted from Gaussian elimination and graph theory. We are able to determine multistationarity of our main example over a 2-dimensional parameter space. We also study a second MAPK model and a symbolic grid sampling technique which can locate such regions in 3-dimensional parameter space.}, }
Endnote
%0 Report %A Bradford, Russell %A Davenport, James H. %A England, Matthew %A Errami, Hassan %A Gerdt, Vladimir %A Grigoriev, Dima %A Hoyt, Charles %A Ko&#353;ta, Marek %A Radulescu, Ovidiu %A Sturm, Thomas %A Weber, Andreas %+ External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations External Organizations Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks : %G eng %U http://hdl.handle.net/21.11116/0000-0002-FF3C-D %U http://arxiv.org/abs/1902.04882 %D 2019 %X We consider a problem from biological network analysis of determining regions in a parameter space over which there are multiple steady states for positive real values of variables and parameters. We describe multiple approaches to address the problem using tools from Symbolic Computation. We describe how progress was made to achieve semi-algebraic descriptions of the multistationarity regions of parameter space, and compare symbolic results to numerical methods. The biological networks studied are models of the mitogen-activated protein kinases (MAPK) network which has already consumed considerable effort using special insights into its structure of corresponding models. Our main example is a model with 11 equations in 11 variables and 19 parameters, 3 of which are of interest for symbolic treatment. The model also imposes positivity conditions on all variables and parameters. We apply combinations of symbolic computation methods designed for mixed equality/inequality systems, specifically virtual substitution, lazy real triangularization and cylindrical algebraic decomposition, as well as a simplification technique adapted from Gaussian elimination and graph theory. We are able to determine multistationarity of our main example over a 2-dimensional parameter space. We also study a second MAPK model and a symbolic grid sampling technique which can locate such regions in 3-dimensional parameter space. %K Computer Science, Symbolic Computation, cs.SC
Bromberger, M., Fleury, M., Schwarz, S., & Weidenbach, C. (2019). SPASS-SATT: A CDCL(LA) Solver. In Automated Deduction -- CADE 27. Natal, Brazil: Springer. doi:10.1007/978-3-030-29436-6_7
Export
BibTeX
@inproceedings{Bromberger_CADE2019, TITLE = {{SPASS-SATT}: {A CDCL(LA)} Solver}, AUTHOR = {Bromberger, Martin and Fleury, Mathias and Schwarz, Simon and Weidenbach, Christoph}, LANGUAGE = {eng}, ISSN = {0302-9743}, ISBN = {978-3-030-29435-9}, DOI = {10.1007/978-3-030-29436-6_7}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Automated Deduction -- CADE 27}, EDITOR = {Fontaine, Pascal}, PAGES = {111--122}, SERIES = {Lecture Notes in Artificial Intelligence}, VOLUME = {11716}, ADDRESS = {Natal, Brazil}, }
Endnote
%0 Conference Proceedings %A Bromberger, Martin %A Fleury, Mathias %A Schwarz, Simon %A Weidenbach, Christoph %+ Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society %T SPASS-SATT: A CDCL(LA) Solver : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8846-3 %R 10.1007/978-3-030-29436-6_7 %D 2019 %B 27th International Conference on Automated Deduction %Z date of event: 2019-08-27 - 2019-08-30 %C Natal, Brazil %B Automated Deduction -- CADE 27 %E Fontaine, Pascal %P 111 - 122 %I Springer %@ 978-3-030-29435-9 %B Lecture Notes in Artificial Intelligence %N 11716 %@ false
Bromberger, M. (2019). Decision Procedures for Linear Arithmetic. Universität des Saarlandes, Saarbrücken.
Export
BibTeX
@phdthesis{Bromberger_2019, TITLE = {Decision Procedures for Linear Arithmetic}, AUTHOR = {Bromberger, Martin}, LANGUAGE = {eng}, DOI = {10.22028/D291-30636}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, }
Endnote
%0 Thesis %A Bromberger, Martin %Y Weidenbach, Christoph %A referee: Sturm, Thomas %+ Automation of Logic, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society %T Decision Procedures for Linear Arithmetic : %G eng %U http://hdl.handle.net/21.11116/0000-0007-713E-5 %R 10.22028/D291-30636 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2019 %P 341 p. %V phd %9 phd %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/28955
Cropper, A., & Tourret, S. (2019). Logical Reduction of Metarules. Machine Learning (Proc. ILP 2019), 109. doi:10.1007/s10994-019-05834-x
Export
BibTeX
@article{Cropper2019, TITLE = {Logical Reduction of Metarules}, AUTHOR = {Cropper, Andrew and Tourret, Sophie}, LANGUAGE = {eng}, ISSN = {0885-6125}, DOI = {10.1007/s10994-019-05834-x}, PUBLISHER = {Springer}, ADDRESS = {Dordrecht}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, JOURNAL = {Machine Learning (Proc. ILP)}, VOLUME = {109}, PAGES = {1323--1369}, BOOKTITLE = {Special Issue of the Inductive Logic Programming (ILP) 2019}, EDITOR = {Kazakov, Dimitar and Zelezny, Filip}, }
Endnote
%0 Journal Article %A Cropper, Andrew %A Tourret, Sophie %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society %T Logical Reduction of Metarules : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8859-E %R 10.1007/s10994-019-05834-x %7 2019 %D 2019 %J Machine Learning %V 109 %& 1323 %P 1323 - 1369 %I Springer %C Dordrecht %@ false %B Special Issue of the Inductive Logic Programming (ILP) 2019 %O ILP 2019 The 29th International Conference on Inductive Logic Programming. 3-5 Sep 2019, Plovdiv, Bulgaria
Fiori, A., & Weidenbach, C. (2019). SCL Clause Learning from Simple Models. In Automated Deduction -- CADE 27. Natal, Brazil: Springer. doi:10.1007/978-3-030-29436-6_14
Export
BibTeX
@inproceedings{Fiori_CADE2019, TITLE = {{SCL} Clause Learning from Simple Models}, AUTHOR = {Fiori, Alberto and Weidenbach, Christoph}, LANGUAGE = {eng}, ISSN = {0302-9743}, ISBN = {978-3-030-29435-9}, DOI = {10.1007/978-3-030-29436-6_14}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Automated Deduction -- CADE 27}, EDITOR = {Fontaine, Pascal}, PAGES = {233--249}, SERIES = {Lecture Notes in Artificial Intelligence}, VOLUME = {11716}, ADDRESS = {Natal, Brazil}, }
Endnote
%0 Conference Proceedings %A Fiori, Alberto %A Weidenbach, Christoph %+ Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society %T SCL Clause Learning from Simple Models : %G eng %U http://hdl.handle.net/21.11116/0000-0005-883F-C %R 10.1007/978-3-030-29436-6_14 %D 2019 %B 27th International Conference on Automated Deduction %Z date of event: 2019-08-27 - 2019-08-30 %C Natal, Brazil %B Automated Deduction -- CADE 27 %E Fontaine, Pascal %P 233 - 249 %I Springer %@ 978-3-030-29435-9 %B Lecture Notes in Artificial Intelligence %N 11716 %@ false
Fleury, M., & Schurr, H.-J. (2019). Reconstructing veriT Proofs in Isabelle/HOL. Electronic Proceedings in Theoretical Computer Science (Proc. PxTP 2019), (301). doi:10.4204/EPTCS.301.6
(arXiv: 1908.09480)
Abstract
Automated theorem provers are now commonly used within interactive theorem provers to discharge an increasingly large number of proof obligations. To maintain the trustworthiness of a proof, the automatically found proof must be verified inside the proof assistant. We present here a reconstruction procedure in the proof assistant Isabelle/HOL for proofs generated by the satisfiability modulo theories solver veriT which is part of the smt tactic. We describe in detail the architecture of our improved reconstruction method and the challenges we faced in designing it. Our experiments show that the veriT-powered smt tactic is regularly suggested by Sledgehammer as the fastest method to automatically solve proof goals.
Export
BibTeX
@article{Fleury_PxTP2019, TITLE = {Reconstructing {veriT} Proofs in {I}sabelle/{HOL}}, AUTHOR = {Fleury, Mathias and Schurr, Hans-J{\"o}rg}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1908.09480}, DOI = {10.4204/EPTCS.301.6}, EPRINT = {1908.09480}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {Automated theorem provers are now commonly used within interactive theorem provers to discharge an increasingly large number of proof obligations. To maintain the trustworthiness of a proof, the automatically found proof must be verified inside the proof assistant. We present here a reconstruction procedure in the proof assistant Isabelle/HOL for proofs generated by the satisfiability modulo theories solver veriT which is part of the smt tactic. We describe in detail the architecture of our improved reconstruction method and the challenges we faced in designing it. Our experiments show that the veriT-powered smt tactic is regularly suggested by Sledgehammer as the fastest method to automatically solve proof goals.}, JOURNAL = {Electronic Proceedings in Theoretical Computer Science (Proc. PxTP)}, NUMBER = {301}, PAGES = {36--50}, BOOKTITLE = {Proceedings Sixth Workshop on Proof eXchange for Theorem Proving (PxTP 2019)}, EDITOR = {Reis, Giselle and Barbosa, Haniel}, }
Endnote
%0 Journal Article %A Fleury, Mathias %A Schurr, Hans-J&#246;rg %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Reconstructing veriT Proofs in Isabelle/HOL : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8879-A %R 10.4204/EPTCS.301.6 %U http://arxiv.org/abs/1908.09480 %7 2019 %D 2019 %X Automated theorem provers are now commonly used within interactive theorem provers to discharge an increasingly large number of proof obligations. To maintain the trustworthiness of a proof, the automatically found proof must be verified inside the proof assistant. We present here a reconstruction procedure in the proof assistant Isabelle/HOL for proofs generated by the satisfiability modulo theories solver veriT which is part of the smt tactic. We describe in detail the architecture of our improved reconstruction method and the challenges we faced in designing it. Our experiments show that the veriT-powered smt tactic is regularly suggested by Sledgehammer as the fastest method to automatically solve proof goals. %K Computer Science, Logic in Computer Science, cs.LO %J Electronic Proceedings in Theoretical Computer Science %O EPTCS %N 301 %& 36 %P 36 - 50 %B Proceedings Sixth Workshop on Proof eXchange for Theorem Proving %O PxTP 2019 Natal, Brazil, August 26, 2019
Fleury, M. (2019). Optimizing a Verified SAT Solver. In NASA Formal Methods (NFM 2019). Houston, TX, USA: Springer. doi:10.1007/978-3-030-20652-9_10
Export
BibTeX
@inproceedings{DBLP:conf/nfm/Fleury19, TITLE = {Optimizing a Verified {SAT} Solver}, AUTHOR = {Fleury, Mathias}, LANGUAGE = {eng}, ISBN = {978-3-030-20651-2}, DOI = {10.1007/978-3-030-20652-9_10}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {NASA Formal Methods (NFM 2019)}, EDITOR = {Badger, Julia M. and Rozier, Kristin Yvonne}, PAGES = {148--165}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {11460}, ADDRESS = {Houston, TX, USA}, }
Endnote
%0 Conference Proceedings %A Fleury, Mathias %+ Automation of Logic, MPI for Informatics, Max Planck Society %T Optimizing a Verified SAT Solver : %G eng %U http://hdl.handle.net/21.11116/0000-0004-86AA-5 %R 10.1007/978-3-030-20652-9_10 %D 2019 %B 1th NASA Formal Methods Symposium %Z date of event: 2019-05-07 - 2019-05-09 %C Houston, TX, USA %B NASA Formal Methods %E Badger, Julia M.; Rozier, Kristin Yvonne %P 148 - 165 %I Springer %@ 978-3-030-20651-2 %B Lecture Notes in Computer Science %N 11460
Frohn, F., & Giesl, J. (2019a). Proving Non-Termination via Loop Acceleration. In Formal Methods in Computer Aided Design (FMCAD 2019). San Jose, CA, USA: IEEE. doi:10.23919/FMCAD.2019.8894271
Export
BibTeX
@inproceedings{Frohn_FMCAD2019, TITLE = {Proving Non-Termination via Loop Acceleration}, AUTHOR = {Frohn, Florian and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, ISBN = {978-0-9835678-9-9}, DOI = {10.23919/FMCAD.2019.8894271}, PUBLISHER = {IEEE}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Formal Methods in Computer Aided Design (FMCAD 2019)}, PAGES = {221--230}, ADDRESS = {San Jose, CA, USA}, }
Endnote
%0 Conference Proceedings %A Frohn, Florian %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Proving Non-Termination via Loop Acceleration : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7EDD-4 %R 10.23919/FMCAD.2019.8894271 %D 2019 %B 19th International Conference on Formal Methods in Computer Aided Design %Z date of event: 2019-10-22 - 2019-10-25 %C San Jose, CA, USA %B Formal Methods in Computer Aided Design %P 221 - 230 %I IEEE %@ 978-0-9835678-9-9
Frohn, F., & Giesl, J. (2019b). Termination of Triangular Integer Loops is Decidable. In Computer Aided Verification (CAV 2019). York City, NY, USA: Springer. doi:10.1007/978-3-030-25543-5_24
Export
BibTeX
@inproceedings{Frohn_CAV2019, TITLE = {Termination of Triangular Integer Loops is Decidable}, AUTHOR = {Frohn, Florian and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, ISBN = {978-3-030-25543-5}, DOI = {10.1007/978-3-030-25543-5_24}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Computer Aided Verification (CAV 2019)}, EDITOR = {Dillig, Isil and Tasiran, Serdar}, PAGES = {426--444}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {11562}, ADDRESS = {York City, NY, USA}, }
Endnote
%0 Conference Proceedings %A Frohn, Florian %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Termination of Triangular Integer Loops is Decidable : %G eng %U http://hdl.handle.net/21.11116/0000-0007-7E8E-D %R 10.1007/978-3-030-25543-5_24 %D 2019 %B 31st International Conference on Computer-Aided Verification %Z date of event: 2019-07-15 - 2019-07-18 %C York City, NY, USA %B Computer Aided Verification %E Dillig, Isil; Tasiran, Serdar %P 426 - 444 %I Springer %@ 978-3-030-25543-5 %B Lecture Notes in Computer Science %N 11562
Frohn, F., Naaf, M., Brockschmidt, M., & Giesl, J. (2019). Inferring Lower Runtime Bounds for Integer Programs. Retrieved from https://arxiv.org/abs/1911.01077
(arXiv: 1911.01077)
Abstract
We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples.
Export
BibTeX
@online{Frohn_arXIv1911.01077, TITLE = {Inferring Lower Runtime Bounds for Integer Programs}, AUTHOR = {Frohn, Florian and Naaf, Matthias and Brockschmidt, Marc and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/1911.01077}, EPRINT = {1911.01077}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples.}, }
Endnote
%0 Report %A Frohn, Florian %A Naaf, Matthias %A Brockschmidt, Marc %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations External Organizations External Organizations %T Inferring Lower Runtime Bounds for Integer Programs : %G eng %U http://hdl.handle.net/21.11116/0000-0007-CEF3-F %U https://arxiv.org/abs/1911.01077 %D 2019 %X We present a technique to infer lower bounds on the worst-case runtime complexity of integer programs, where in contrast to earlier work, our approach is not restricted to tail-recursion. Our technique constructs symbolic representations of program executions using a framework for iterative, under-approximating program simplification. The core of this simplification is a method for (under-approximating) program acceleration based on recurrence solving and a variation of ranking functions. Afterwards, we deduce asymptotic lower bounds from the resulting simplified programs using a special-purpose calculus and an SMT encoding. We implemented our technique in our tool LoAT and show that it infers non-trivial lower bounds for a large class of examples. %K Computer Science, Logic in Computer Science, cs.LO,Computer Science, Programming Languages, cs.PL
Frohn, F., Hark, M., & Giesl, J. (2019). On the Decidability of Termination for Polynomial Loops. Retrieved from https://arxiv.org/abs/1910.11588
(arXiv: 1910.11588)
Abstract
We consider the termination problem for triangular weakly non-linear loops (twn-loops) over some ring $\mathcal{S}$ like $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$. Essentially, the guard of such a loop is an arbitrary Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment $(x_1, \ldots, x_d) \longleftarrow (c_1 \cdot x_1 + p_1, \ldots, c_d \cdot x_d + p_d)$ where each $x_i$ is a variable, $c_i \in \mathcal{S}$, and each $p_i$ is a (possibly non-linear) polynomial over $\mathcal{S}$ and the variables $x_{i+1},\ldots,x_{d}$. We present a reduction from the question of termination to the existential fragment of the first-order theory of $\mathcal{S}$ and $\mathbb{R}$. For loops over $\mathbb{R}$, our reduction entails decidability of termination. For loops over $\mathbb{Z}$ and $\mathbb{Q}$, it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $\mathbb{R}$, which can also be checked via our reduction. This transformation also allows us to prove tight complexity bounds for the termination problem for two important classes of loops which can always be transformed into twn-loops.
Export
BibTeX
@online{Frohn_arXiv1910.11588, TITLE = {On the Decidability of Termination for Polynomial Loops}, AUTHOR = {Frohn, Florian and Hark, Marcel and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/1910.11588}, EPRINT = {1910.11588}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the termination problem for triangular weakly non-linear loops (twn-loops) over some ring $\mathcal{S}$ like $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$. Essentially, the guard of such a loop is an arbitrary Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment $(x_1, \ldots, x_d) \longleftarrow (c_1 \cdot x_1 + p_1, \ldots, c_d \cdot x_d + p_d)$ where each $x_i$ is a variable, $c_i \in \mathcal{S}$, and each $p_i$ is a (possibly non-linear) polynomial over $\mathcal{S}$ and the variables $x_{i+1},\ldots,x_{d}$. We present a reduction from the question of termination to the existential fragment of the first-order theory of $\mathcal{S}$ and $\mathbb{R}$. For loops over $\mathbb{R}$, our reduction entails decidability of termination. For loops over $\mathbb{Z}$ and $\mathbb{Q}$, it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $\mathbb{R}$, which can also be checked via our reduction. This transformation also allows us to prove tight complexity bounds for the termination problem for two important classes of loops which can always be transformed into twn-loops.}, }
Endnote
%0 Report %A Frohn, Florian %A Hark, Marcel %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations External Organizations %T On the Decidability of Termination for Polynomial Loops : %G eng %U http://hdl.handle.net/21.11116/0000-0007-CEE8-C %U https://arxiv.org/abs/1910.11588 %D 2019 %X We consider the termination problem for triangular weakly non-linear loops (twn-loops) over some ring $\mathcal{S}$ like $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$. Essentially, the guard of such a loop is an arbitrary Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment $(x_1, \ldots, x_d) \longleftarrow (c_1 \cdot x_1 + p_1, \ldots, c_d \cdot x_d + p_d)$ where each $x_i$ is a variable, $c_i \in \mathcal{S}$, and each $p_i$ is a (possibly non-linear) polynomial over $\mathcal{S}$ and the variables $x_{i+1},\ldots,x_{d}$. We present a reduction from the question of termination to the existential fragment of the first-order theory of $\mathcal{S}$ and $\mathbb{R}$. For loops over $\mathbb{R}$, our reduction entails decidability of termination. For loops over $\mathbb{Z}$ and $\mathbb{Q}$, it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $\mathbb{R}$, which can also be checked via our reduction. This transformation also allows us to prove tight complexity bounds for the termination problem for two important classes of loops which can always be transformed into twn-loops. %K Computer Science, Logic in Computer Science, cs.LO
Frohn, F., & Giesl, J. (2019c). Proving Non-Termination via Loop Acceleration. Retrieved from https://arxiv.org/abs/1905.11187
(arXiv: 1905.11187)
Abstract
We present the first approach to prove non-termination of integer programs that is based on loop acceleration. If our technique cannot show non-termination of a loop, it tries to accelerate it instead in order to find paths to other non-terminating loops automatically. The prerequisites for our novel loop acceleration technique generalize a simple yet effective non-termination criterion. Thus, we can use the same program transformations to facilitate both non-termination proving and loop acceleration. In particular, we present a novel invariant inference technique that is tailored to our approach. An extensive evaluation of our fully automated tool LoAT shows that it is competitive with the state of the art.
Export
BibTeX
@online{Frohn_arXiv1905.11187, TITLE = {Proving Non-Termination via Loop Acceleration}, AUTHOR = {Frohn, Florian and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/1905.11187}, EPRINT = {1905.11187}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We present the first approach to prove non-termination of integer programs that is based on loop acceleration. If our technique cannot show non-termination of a loop, it tries to accelerate it instead in order to find paths to other non-terminating loops automatically. The prerequisites for our novel loop acceleration technique generalize a simple yet effective non-termination criterion. Thus, we can use the same program transformations to facilitate both non-termination proving and loop acceleration. In particular, we present a novel invariant inference technique that is tailored to our approach. An extensive evaluation of our fully automated tool LoAT shows that it is competitive with the state of the art.}, }
Endnote
%0 Report %A Frohn, Florian %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Proving Non-Termination via Loop Acceleration : %G eng %U http://hdl.handle.net/21.11116/0000-0007-CEE0-4 %U https://arxiv.org/abs/1905.11187 %D 2019 %X We present the first approach to prove non-termination of integer programs that is based on loop acceleration. If our technique cannot show non-termination of a loop, it tries to accelerate it instead in order to find paths to other non-terminating loops automatically. The prerequisites for our novel loop acceleration technique generalize a simple yet effective non-termination criterion. Thus, we can use the same program transformations to facilitate both non-termination proving and loop acceleration. In particular, we present a novel invariant inference technique that is tailored to our approach. An extensive evaluation of our fully automated tool LoAT shows that it is competitive with the state of the art. %K Computer Science, Logic in Computer Science, cs.LO
Frohn, F., & Giesl, J. (2019d). Termination of Triangular Integer Loops is Decidable. Retrieved from https://arxiv.org/abs/1905.08664
(arXiv: 1905.08664)
Abstract
We consider the problem whether termination of affine integer loops is decidable. Since Tiwari conjectured decidability in 2004, only special cases have been solved. We complement this work by proving decidability for the case that the update matrix is triangular.
Export
BibTeX
@online{Froh_arXIv1905.08664, TITLE = {Termination of Triangular Integer Loops is Decidable}, AUTHOR = {Frohn, Florian and Giesl, J{\"u}rgen}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/1905.08664}, EPRINT = {1905.08664}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the problem whether termination of affine integer loops is decidable. Since Tiwari conjectured decidability in 2004, only special cases have been solved. We complement this work by proving decidability for the case that the update matrix is triangular.}, }
Endnote
%0 Report %A Frohn, Florian %A Giesl, J&#252;rgen %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Termination of Triangular Integer Loops is Decidable : %G eng %U http://hdl.handle.net/21.11116/0000-0007-CED1-5 %U https://arxiv.org/abs/1905.08664 %D 2019 %X We consider the problem whether termination of affine integer loops is decidable. Since Tiwari conjectured decidability in 2004, only special cases have been solved. We complement this work by proving decidability for the case that the update matrix is triangular. %K Computer Science, Logic in Computer Science, cs.LO
Grigoriev, D., Iosif, A., Rahkooy, H., Sturm, T., & Weber, A. (2019). Efficiently and Effectively Recognizing Toricity of Steady State Varieties. Retrieved from http://arxiv.org/abs/1910.04100
(arXiv: 1910.04100)
Abstract
We consider the problem of testing whether the points in a complex or real variety with non-zero coordinates form a multiplicative group or, more generally, a coset of a multiplicative group. For the coset case, we study the notion of shifted toric varieties which generalizes the notion of toric varieties. This requires a geometric view on the varieties rather than an algebraic view on the ideals. We present algorithms and computations on 129 models from the BioModels repository testing for group and coset structures over both the complex numbers and the real numbers. Our methods over the complex numbers are based on Gr\"obner basis techniques and binomiality tests. Over the real numbers we use first-order characterizations and employ real quantifier elimination. In combination with suitable prime decompositions and restrictions to subspaces it turns out that almost all models show coset structure. Beyond our practical computations, we give upper bounds on the asymptotic worst-case complexity of the corresponding problems by proposing single exponential algorithms that test complex or real varieties for toricity or shifted toricity. In the positive case, these algorithms produce generating binomials. In addition, we propose an asymptotically fast algorithm for testing membership in a binomial variety over the algebraic closure of the rational numbers.
Export
BibTeX
@online{Grigoriev_arXiv1910.04100, TITLE = {Efficiently and Effectively Recognizing Toricity of Steady State Varieties}, AUTHOR = {Grigoriev, Dima and Iosif, Alexandru and Rahkooy, Hamid and Sturm, Thomas and Weber, Andreas}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1910.04100}, EPRINT = {1910.04100}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {We consider the problem of testing whether the points in a complex or real variety with non-zero coordinates form a multiplicative group or, more generally, a coset of a multiplicative group. For the coset case, we study the notion of shifted toric varieties which generalizes the notion of toric varieties. This requires a geometric view on the varieties rather than an algebraic view on the ideals. We present algorithms and computations on 129 models from the BioModels repository testing for group and coset structures over both the complex numbers and the real numbers. Our methods over the complex numbers are based on Gr\"obner basis techniques and binomiality tests. Over the real numbers we use first-order characterizations and employ real quantifier elimination. In combination with suitable prime decompositions and restrictions to subspaces it turns out that almost all models show coset structure. Beyond our practical computations, we give upper bounds on the asymptotic worst-case complexity of the corresponding problems by proposing single exponential algorithms that test complex or real varieties for toricity or shifted toricity. In the positive case, these algorithms produce generating binomials. In addition, we propose an asymptotically fast algorithm for testing membership in a binomial variety over the algebraic closure of the rational numbers.}, }
Endnote
%0 Report %A Grigoriev, Dima %A Iosif, Alexandru %A Rahkooy, Hamid %A Sturm, Thomas %A Weber, Andreas %+ External Organizations External Organizations External Organizations Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T Efficiently and Effectively Recognizing Toricity of Steady State Varieties : %G eng %U http://hdl.handle.net/21.11116/0000-0005-890F-1 %U http://arxiv.org/abs/1910.04100 %D 2019 %X We consider the problem of testing whether the points in a complex or real variety with non-zero coordinates form a multiplicative group or, more generally, a coset of a multiplicative group. For the coset case, we study the notion of shifted toric varieties which generalizes the notion of toric varieties. This requires a geometric view on the varieties rather than an algebraic view on the ideals. We present algorithms and computations on 129 models from the BioModels repository testing for group and coset structures over both the complex numbers and the real numbers. Our methods over the complex numbers are based on Gr\"obner basis techniques and binomiality tests. Over the real numbers we use first-order characterizations and employ real quantifier elimination. In combination with suitable prime decompositions and restrictions to subspaces it turns out that almost all models show coset structure. Beyond our practical computations, we give upper bounds on the asymptotic worst-case complexity of the corresponding problems by proposing single exponential algorithms that test complex or real varieties for toricity or shifted toricity. In the positive case, these algorithms produce generating binomials. In addition, we propose an asymptotically fast algorithm for testing membership in a binomial variety over the algebraic closure of the rational numbers. %K Quantitative Biology, Molecular Networks, q-bio.MN,Computer Science, Symbolic Computation, cs.SC,Mathematics, Algebraic Geometry, math.AG
Schlichtkrull, A., Blanchette, J. C., & Traytel, D. (2019). A Verified Prover Based on Ordered Resolution. In CPP’19, 8th ACM SIGPLAN International Conference on Certified Programs and Proofs. Cascais, Portugal: ACM. doi:10.1145/3293880.3294100
Export
BibTeX
@inproceedings{Schlichtkrull_CPP2019, TITLE = {A Verified Prover Based on Ordered Resolution}, AUTHOR = {Schlichtkrull, Anders and Blanchette, Jasmin Christian and Traytel, Dmitriy}, LANGUAGE = {eng}, ISBN = {978-1-4503-6222-1}, DOI = {10.1145/3293880.3294100}, PUBLISHER = {ACM}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {CPP'19, 8th ACM SIGPLAN International Conference on Certified Programs and Proofs}, EDITOR = {Mahboubi, Assia and Myreen, Magnus O.}, PAGES = {152--165}, ADDRESS = {Cascais, Portugal}, }
Endnote
%0 Conference Proceedings %A Schlichtkrull, Anders %A Blanchette, Jasmin Christian %A Traytel, Dmitriy %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T A Verified Prover Based on Ordered Resolution : %G eng %U http://hdl.handle.net/21.11116/0000-0002-E59E-A %R 10.1145/3293880.3294100 %D 2019 %B 8th ACM SIGPLAN International Conference on Certified Programs and Proofs %Z date of event: 2019-01-14 - 2019-01-15 %C Cascais, Portugal %B CPP'19 %E Mahboubi, Assia; Myreen, Magnus O. %P 152 - 165 %I ACM %@ 978-1-4503-6222-1
Teucke, A., Voigt, M., & Weidenbach, C. (2019a). On the Expressivity and Applicability of Model Representation Formalisms. In Frontiers of Combining Systems (FroCos 2019). London, UK: Springer. doi:10.1007/978-3-030-29007-8_2
Export
BibTeX
@inproceedings{Teucke_FroCos2019, TITLE = {On the Expressivity and Applicability of Model Representation Formalisms}, AUTHOR = {Teucke, Andreas and Voigt, Marco and Weidenbach, Christoph}, LANGUAGE = {eng}, ISSN = {302-9743}, ISBN = {978-3-030-29006-1}, DOI = {10.1007/978-3-030-29007-8_2}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Frontiers of Combining Systems (FroCos 2019)}, EDITOR = {Herzig, Andreas and Popescu, Andrei}, PAGES = {22--39}, SERIES = {Lecture Notes in Artificial Intelligence}, VOLUME = {11715}, ADDRESS = {London, UK}, }
Endnote
%0 Conference Proceedings %A Teucke, Andreas %A Voigt, Marco %A Weidenbach, Christoph %+ Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society %T On the Expressivity and Applicability of Model Representation Formalisms : %G eng %U http://hdl.handle.net/21.11116/0000-0005-883B-0 %R 10.1007/978-3-030-29007-8_2 %D 2019 %B 12th International Symposium on Frontiers of Combining Systems %Z date of event: 2019-09-04 - 2019-09-06 %C London, UK %B Frontiers of Combining Systems %E Herzig, Andreas; Popescu, Andrei %P 22 - 39 %I Springer %@ 978-3-030-29006-1 %B Lecture Notes in Artificial Intelligence %N 11715 %@ false
Teucke, A., Voigt, M., & Weidenbach, C. (2019b). On the Expressivity and Applicability of Model Representation Formalisms. Retrieved from http://arxiv.org/abs/1905.03651
(arXiv: 1905.03651)
Abstract
A number of first-order calculi employ an explicit model representation formalism for automated reasoning and for detecting satisfiability. Many of these formalisms can represent infinite Herbrand models. The first-order fragment of monadic, shallow, linear, Horn (MSLH) clauses, is such a formalism used in the approximation refinement calculus. Our first result is a finite model property for MSLH clause sets. Therefore, MSLH clause sets cannot represent models of clause sets with inherently infinite models. Through a translation to tree automata, we further show that this limitation also applies to the linear fragments of implicit generalizations, which is the formalism used in the model-evolution calculus, to atoms with disequality constraints, the formalisms used in the non-redundant clause learning calculus (NRCL), and to atoms with membership constraints, a formalism used for example in decision procedures for algebraic data types. Although these formalisms cannot represent models of clause sets with inherently infinite models, through an additional approximation step they can. This is our second main result. For clause sets including the definition of an equivalence relation with the help of an additional, novel approximation, called reflexive relation splitting, the approximation refinement calculus can automatically show satisfiability through the MSLH clause set formalism.
Export
BibTeX
@online{Teucke_arXiv1905.03651, TITLE = {On the Expressivity and Applicability of Model Representation Formalisms}, AUTHOR = {Teucke, Andreas and Voigt, Marco and Weidenbach, Christoph}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1905.03651}, EPRINT = {1905.03651}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {A number of first-order calculi employ an explicit model representation formalism for automated reasoning and for detecting satisfiability. Many of these formalisms can represent infinite Herbrand models. The first-order fragment of monadic, shallow, linear, Horn (MSLH) clauses, is such a formalism used in the approximation refinement calculus. Our first result is a finite model property for MSLH clause sets. Therefore, MSLH clause sets cannot represent models of clause sets with inherently infinite models. Through a translation to tree automata, we further show that this limitation also applies to the linear fragments of implicit generalizations, which is the formalism used in the model-evolution calculus, to atoms with disequality constraints, the formalisms used in the non-redundant clause learning calculus (NRCL), and to atoms with membership constraints, a formalism used for example in decision procedures for algebraic data types. Although these formalisms cannot represent models of clause sets with inherently infinite models, through an additional approximation step they can. This is our second main result. For clause sets including the definition of an equivalence relation with the help of an additional, novel approximation, called reflexive relation splitting, the approximation refinement calculus can automatically show satisfiability through the MSLH clause set formalism.}, }
Endnote
%0 Report %A Teucke, Andreas %A Voigt, Marco %A Weidenbach, Christoph %+ Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society %T On the Expressivity and Applicability of Model Representation Formalisms : %G eng %U http://hdl.handle.net/21.11116/0000-0004-031B-B %U http://arxiv.org/abs/1905.03651 %D 2019 %X A number of first-order calculi employ an explicit model representation formalism for automated reasoning and for detecting satisfiability. Many of these formalisms can represent infinite Herbrand models. The first-order fragment of monadic, shallow, linear, Horn (MSLH) clauses, is such a formalism used in the approximation refinement calculus. Our first result is a finite model property for MSLH clause sets. Therefore, MSLH clause sets cannot represent models of clause sets with inherently infinite models. Through a translation to tree automata, we further show that this limitation also applies to the linear fragments of implicit generalizations, which is the formalism used in the model-evolution calculus, to atoms with disequality constraints, the formalisms used in the non-redundant clause learning calculus (NRCL), and to atoms with membership constraints, a formalism used for example in decision procedures for algebraic data types. Although these formalisms cannot represent models of clause sets with inherently infinite models, through an additional approximation step they can. This is our second main result. For clause sets including the definition of an equivalence relation with the help of an additional, novel approximation, called reflexive relation splitting, the approximation refinement calculus can automatically show satisfiability through the MSLH clause set formalism. %K Computer Science, Logic in Computer Science, cs.LO
Tourret, S., & Cropper, A. (2019). SLD-Resolution Reduction of Second-Order Horn Fragments. In Logics in Artificial Intelligence (JELIA 2019). Rende, Italy: Springer. doi:10.1007/978-3-030-19570-0_17
Export
BibTeX
@inproceedings{Tourret_JELIA2019, TITLE = {{SLD}-Resolution Reduction of Second-Order {H}orn Fragments}, AUTHOR = {Tourret, Sophie and Cropper, Andrew}, LANGUAGE = {eng}, ISBN = {978-3-030-19569-4}, DOI = {10.1007/978-3-030-19570-0_17}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Logics in Artificial Intelligence (JELIA 2019)}, EDITOR = {Calimeri, Francesco and Leone, Nicola and Manna, Marco}, PAGES = {259--276}, SERIES = {Lecture Notes in Artificial Intelligence}, VOLUME = {11468}, ADDRESS = {Rende, Italy}, }
Endnote
%0 Conference Proceedings %A Tourret, Sophie %A Cropper, Andrew %+ Automation of Logic, MPI for Informatics, Max Planck Society External Organizations %T SLD-Resolution Reduction of Second-Order Horn Fragments : %G eng %U http://hdl.handle.net/21.11116/0000-0002-D2B3-6 %R 10.1007/978-3-030-19570-0_17 %D 2019 %B 16th European Conference on Logics in Artificial Intelligence %Z date of event: 2019-05-08 - 2019-05-10 %C Rende, Italy %B Logics in Artificial Intelligence %E Calimeri, Francesco; Leone, Nicola; Manna, Marco %P 259 - 276 %I Springer %@ 978-3-030-19569-4 %B Lecture Notes in Artificial Intelligence %N 11468
Voigt, M. (2019a). Separateness of Variables - A Novel Perspective on Decidable First-Order Fragments. Retrieved from http://arxiv.org/abs/1911.11500
(arXiv: 1911.11500)
Abstract
The classical decision problem, as it is understood today, is the quest for a delineation between the decidable and the undecidable parts of first-order logic based on elegant syntactic criteria. In this paper, we treat the concept of separateness of variables and explore its applicability to the classical decision problem. Two disjoint sets of first-order variables are separated in a given formula if variables from the two sets never co-occur in any atom of that formula. This simple notion facilitates extending many well-known decidable first-order fragments significantly and in a way that preserves decidability. We will demonstrate that for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Altogether, we will investigate nine such extensions more closely. Interestingly, each of them contains the relational monadic first-order fragment without equality. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In three cases the succinctness gap cannot be bounded using any elementary function.
Export
BibTeX
@online{VoigtSep2019, TITLE = {Separateness of Variables -- A Novel Perspective on Decidable First-Order Fragments}, AUTHOR = {Voigt, Marco}, LANGUAGE = {eng}, URL = {http://arxiv.org/abs/1911.11500}, EPRINT = {1911.11500}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {The classical decision problem, as it is understood today, is the quest for a delineation between the decidable and the undecidable parts of first-order logic based on elegant syntactic criteria. In this paper, we treat the concept of separateness of variables and explore its applicability to the classical decision problem. Two disjoint sets of first-order variables are separated in a given formula if variables from the two sets never co-occur in any atom of that formula. This simple notion facilitates extending many well-known decidable first-order fragments significantly and in a way that preserves decidability. We will demonstrate that for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Altogether, we will investigate nine such extensions more closely. Interestingly, each of them contains the relational monadic first-order fragment without equality. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In three cases the succinctness gap cannot be bounded using any elementary function.}, }
Endnote
%0 Report %A Voigt, Marco %+ Automation of Logic, MPI for Informatics, Max Planck Society %T Separateness of Variables - A Novel Perspective on Decidable First-Order Fragments : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8D56-C %U http://arxiv.org/abs/1911.11500 %D 2019 %8 26.11.2019 %X The classical decision problem, as it is understood today, is the quest for a delineation between the decidable and the undecidable parts of first-order logic based on elegant syntactic criteria. In this paper, we treat the concept of separateness of variables and explore its applicability to the classical decision problem. Two disjoint sets of first-order variables are separated in a given formula if variables from the two sets never co-occur in any atom of that formula. This simple notion facilitates extending many well-known decidable first-order fragments significantly and in a way that preserves decidability. We will demonstrate that for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Altogether, we will investigate nine such extensions more closely. Interestingly, each of them contains the relational monadic first-order fragment without equality. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In three cases the succinctness gap cannot be bounded using any elementary function. %K Computer Science, Logic in Computer Science, cs.LO
Voigt, M. (2019b). Decidable Fragments of First-Order Logic and of First-Order Linear Arithmetic with Uninterpreted Predicates. Universität des Saarlandes, Saarbrücken.
Abstract
First-order logic is one of the most prominent formalisms in computer science and mathematics. Since there is no algorithm capable of solving its satisfiability problem, first-order logic is said to be undecidable. The classical decision problem is the quest for a delineation between the decidable and the undecidable parts. The results presented in this thesis shed more light on the boundary and open new perspectives on the landscape of known decidable fragments. In the first part we focus on the new concept of separateness of variables and explore its applicability to the classical decision problem and beyond. Two disjoint sets of first-order variables are separated in a given formula if none of its atoms contains variables from both sets. This notion facilitates the definition of decidable extensions of many well-known decidable first-order fragments. We demonstrate this for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In two cases the succinctness gap cannot be bounded using elementary functions. This fact already hints at computationally hard satisfiability problems. Indeed, we derive non-elementary lower bounds for the separated fragment, an extension of the Bernays-Schönfinkel-Ramsey fragment (E*A*-prefix sentences). On the semantic level, separateness of quantified variables may lead to weaker dependences than we encounter in general. We investigate this property in the context of model-checking games. The focus of the second part of the thesis is on linear arithmetic with uninterpreted predicates. Two novel decidable fragments are presented, both based on the Bernays-Schönfinkel-Ramsey fragment. On the negative side, we identify several small fragments of the language for which satisfiability is undecidable.
Export
BibTeX
@phdthesis{voigtphd2019, TITLE = {Decidable Fragments of First-Order Logic and of First-Order Linear Arithmetic with Uninterpreted Predicates}, AUTHOR = {Voigt, Marco}, LANGUAGE = {eng}, DOI = {10.22028/D291-28428}, SCHOOL = {Universit{\"a}t des Saarlandes}, ADDRESS = {Saarbr{\"u}cken}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, ABSTRACT = {First-order logic is one of the most prominent formalisms in computer science and mathematics. Since there is no algorithm capable of solving its satisfiability problem, first-order logic is said to be undecidable. The classical decision problem is the quest for a delineation between the decidable and the undecidable parts. The results presented in this thesis shed more light on the boundary and open new perspectives on the landscape of known decidable fragments. In the first part we focus on the new concept of separateness of variables and explore its applicability to the classical decision problem and beyond. Two disjoint sets of first-order variables are separated in a given formula if none of its atoms contains variables from both sets. This notion facilitates the definition of decidable extensions of many well-known decidable first-order fragments. We demonstrate this for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In two cases the succinctness gap cannot be bounded using elementary functions. This fact already hints at computationally hard satisfiability problems. Indeed, we derive non-elementary lower bounds for the separated fragment, an extension of the Bernays-Sch{\"o}nfinkel-Ramsey fragment (E*A*-prefix sentences). On the semantic level, separateness of quantified variables may lead to weaker dependences than we encounter in general. We investigate this property in the context of model-checking games. The focus of the second part of the thesis is on linear arithmetic with uninterpreted predicates. Two novel decidable fragments are presented, both based on the Bernays-Sch{\"o}nfinkel-Ramsey fragment. On the negative side, we identify several small fragments of the language for which satisfiability is undecidable.}, }
Endnote
%0 Thesis %A Voigt, Marco %Y Weidenbach, Christoph %A referee: Gr&#228;del, Erich %A referee: Leitsch, Alexander %A referee: Sturm, Thomas %+ Automation of Logic, MPI for Informatics, Max Planck Society International Max Planck Research School, MPI for Informatics, Max Planck Society Automation of Logic, MPI for Informatics, Max Planck Society External Organizations External Organizations Automation of Logic, MPI for Informatics, Max Planck Society %T Decidable Fragments of First-Order Logic and of First-Order Linear Arithmetic with Uninterpreted Predicates : %G eng %U http://hdl.handle.net/21.11116/0000-0005-4373-E %R 10.22028/D291-28428 %I Universit&#228;t des Saarlandes %C Saarbr&#252;cken %D 2019 %P 333 p. %V phd %9 phd %X First-order logic is one of the most prominent formalisms in computer science and mathematics. Since there is no algorithm capable of solving its satisfiability problem, first-order logic is said to be undecidable. The classical decision problem is the quest for a delineation between the decidable and the undecidable parts. The results presented in this thesis shed more light on the boundary and open new perspectives on the landscape of known decidable fragments. In the first part we focus on the new concept of separateness of variables and explore its applicability to the classical decision problem and beyond. Two disjoint sets of first-order variables are separated in a given formula if none of its atoms contains variables from both sets. This notion facilitates the definition of decidable extensions of many well-known decidable first-order fragments. We demonstrate this for several prefix fragments, several guarded fragments, the two-variable fragment, and for the fluted fragment. Although the extensions exhibit the same expressive power as the respective originals, certain logical properties can be expressed much more succinctly. In two cases the succinctness gap cannot be bounded using elementary functions. This fact already hints at computationally hard satisfiability problems. Indeed, we derive non-elementary lower bounds for the separated fragment, an extension of the Bernays-Sch&#246;nfinkel-Ramsey fragment (E*A*-prefix sentences). On the semantic level, separateness of quantified variables may lead to weaker dependences than we encounter in general. We investigate this property in the context of model-checking games. The focus of the second part of the thesis is on linear arithmetic with uninterpreted predicates. Two novel decidable fragments are presented, both based on the Bernays-Sch&#246;nfinkel-Ramsey fragment. On the negative side, we identify several small fragments of the language for which satisfiability is undecidable. %U https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/27767
Vukmirović, P., Blanchette, J. C., Cruanes, S., & Schulz, S. (2019). Extending a Brainiac Prover to Lambda-Free Higher-Order Logic. In Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2019). Prague, Czech Republic: Springer. doi:10.1007/978-3-030-17462-0_11
Export
BibTeX
@inproceedings{Vukmirovic_TACAS2019, TITLE = {Extending a Brainiac Prover to Lambda-Free Higher-Order Logic}, AUTHOR = {Vukmirovi{\'c}, Petar and Blanchette, Jasmin Christian and Cruanes, Simon and Schulz, Stephan}, LANGUAGE = {eng}, ISBN = {978-3-030-17461-3}, DOI = {10.1007/978-3-030-17462-0_11}, PUBLISHER = {Springer}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, DATE = {2019}, BOOKTITLE = {Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2019)}, PAGES = {192--210}, SERIES = {Lecture Notes in Computer Science}, VOLUME = {11427}, ADDRESS = {Prague, Czech Republic}, }
Endnote
%0 Conference Proceedings %A Vukmirovi&#263;, Petar %A Blanchette, Jasmin Christian %A Cruanes, Simon %A Schulz, Stephan %+ External Organizations Automation of Logic, MPI for Informatics, Max Planck Society External Organizations External Organizations %T Extending a Brainiac Prover to Lambda-Free Higher-Order Logic : %G eng %U http://hdl.handle.net/21.11116/0000-0004-0326-E %R 10.1007/978-3-030-17462-0_11 %D 2019 %B 25th International Conference on Tools and Algorithms for the Construction and Analysis of Systems %Z date of event: 2019-04-06 - 2019-04-11 %C Prague, Czech Republic %B Tools and Algorithms for the Construction and Analysis of Systems %P 192 - 210 %I Springer %@ 978-3-030-17461-3 %B Lecture Notes in Computer Science %N 11427
Weidenbach, C. (2019). The Challenge of Unifying Semantic and Syntactic Inference Restrictions. Electronic Proceedings in Theoretical Computer Science (Proc. ARCADE 2019), 311. doi:10.4204/EPTCS.311.1
(arXiv: 1912.12966)
Abstract
While syntactic inference restrictions don't play an important role for SAT, they are an essential reasoning technique for more expressive logics, such as first-order logic, or fragments thereof. In particular, they can result in short proofs or model representations. On the other hand, semantically guided inference systems enjoy important properties, such as the generation of solely non-redundant clauses. I discuss to what extend the two paradigms may be unifiable.
Export
BibTeX
@article{Weidenbach_arXiv1912.12966, TITLE = {The Challenge of Unifying Semantic and Syntactic Inference Restrictions}, AUTHOR = {Weidenbach, Christoph}, LANGUAGE = {eng}, URL = {https://arxiv.org/abs/1912.12966}, DOI = {10.4204/EPTCS.311.1}, EPRINT = {1912.12966}, EPRINTTYPE = {arXiv}, YEAR = {2019}, MARGINALMARK = {$\bullet$}, ABSTRACT = {While syntactic inference restrictions don't play an important role for SAT, they are an essential reasoning technique for more expressive logics, such as first-order logic, or fragments thereof. In particular, they can result in short proofs or model representations. On the other hand, semantically guided inference systems enjoy important properties, such as the generation of solely non-redundant clauses. I discuss to what extend the two paradigms may be unifiable.}, JOURNAL = {Electronic Proceedings in Theoretical Computer Science (Proc. ARCADE)}, VOLUME = {311}, PAGES = {5--10}, BOOKTITLE = {Proceedings of the Second International Workshop on Automated Reasoning: Challenges, Applications, Directions, Exemplary Achievements (ARCADE 2019)}, EDITOR = {Suda, Martin and Winkler, Sarah}, }
Endnote
%0 Journal Article %A Weidenbach, Christoph %+ Automation of Logic, MPI for Informatics, Max Planck Society %T The Challenge of Unifying Semantic and Syntactic Inference Restrictions : %G eng %U http://hdl.handle.net/21.11116/0000-0005-8750-8 %U https://arxiv.org/abs/1912.12966 %R 10.4204/EPTCS.311.1 %7 2019 %D 2019 %X While syntactic inference restrictions don't play an important role for SAT, they are an essential reasoning technique for more expressive logics, such as first-order logic, or fragments thereof. In particular, they can result in short proofs or model representations. On the other hand, semantically guided inference systems enjoy important properties, such as the generation of solely non-redundant clauses. I discuss to what extend the two paradigms may be unifiable. %K Computer Science, Logic in Computer Science, cs.LO %J Electronic Proceedings in Theoretical Computer Science %O EPTCS %V 311 %& 5 %P 5 - 10 %B Proceedings of the Second International Workshop on Automated Reasoning: Challenges, Applications, Directions, Exemplary Achievements %O ARCADE 2019 Natal, Brazil, August 26, 2019