# 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_2Export

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_4Export

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ć, 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-5Export

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.3294087Export

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/3290335Export

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š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_7Export

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ät des Saarlandes
%C Saarbrü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-xExport

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_14Export

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.

(arXiv: 1908.09480) *Electronic Proceedings in Theoretical Computer Science (Proc. PxTP 2019)*, (301). doi:10.4204/EPTCS.301.6Abstract

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ö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_10Export

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.8894271Export

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ü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_24Export

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ü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ü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ü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ü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ü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.3294100Export

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_2Export

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_17Export

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ä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ät des Saarlandes
%C Saarbrü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ö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.
%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_11Export

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ć, 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.

(arXiv: 1912.12966) *Electronic Proceedings in Theoretical Computer Science (Proc. ARCADE 2019)*,*311*. doi:10.4204/EPTCS.311.1Abstract

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