# Last Year

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 onCertified 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 onCertified 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 onCertified 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

Cropper, A., & Tourret, S. (2019). Logical Reduction of Metarules.

*Machine Learning (Proc. ILP 2019)*,*First Online*. 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 = {First Online},
PAGES = {1--47},
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 First Online
%& 1
%P 1 - 47
%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 (NGM 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 (NGM 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

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 onCertified 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 onCertified 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 onCertified 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