# Current Year

Baumgartner, P., & Waldmann, U. (2019a). 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

Baumgartner, P., & Waldmann, U. (2019b). 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

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

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

Bradford, R., Davenport, J. H., England, M., Errami, H., Gerdt, V., Grigoriev, D., … Weber, A. (n.d.). Identifying the Parametric Occurrence of Multiple Steady States for some Biological Networks.

(Accepted/in press) *Journal of Symbolic Computation*.Export

BibTeX

@article{BradfordDavenport:19a,
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},
ISSN = {0747-7171},
PUBLISHER = {Academic Press},
ADDRESS = {London},
YEAR = {2019},
PUBLREMARK = {Accepted},
MARGINALMARK = {$\bullet$},
JOURNAL = {Journal of Symbolic Computation},
}

Endnote

%0 Journal Article
%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-F04B-B
%D 2019
%J Journal of Symbolic Computation
%I Academic Press
%C London
%@ false

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

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

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. (2019). 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. (2019).

*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