Search results for "Computer Science::Logic in Computer Science"
showing 10 items of 72 documents
Finiteness in a Minimalist Foundation
2008
We analyze the concepts of finite set and finite subset from the perspective of a minimalist foundational theory which has recently been introduced by Maria Emilia Maietti and the second author. The main feature of that theory and, as a consequence, of our approach is compatibility with other foundational theories such as Zermelo-Fraenkel set theory, Martin-Lof's intuitionistic Type Theory, topos theory, Aczel's CZF, Coquand's Calculus of Constructions. This compatibility forces our arguments to be constructive in a strong sense: no use is made of powerful principles such as the axiom of choice, the power-set axiom, the law of the excluded middle.
Hume’s Fork and Mixed Mathematics
2017
Abstract:Given the sharp distinction that follows from Hume’s Fork, the proper epistemic status of propositions of mixed mathematics seems to be a mystery. On the one hand, mathematical propositions concern the relation of ideas. They are intuitive and demonstratively certain. On the other hand, propositions of mixed mathematics, such as in Hume’s own example, the law of conservation of momentum, are also matter of fact propositions. They concern causal relations between species of objects, and, in this sense, they are not intuitive or demonstratively certain, but probable or provable. In this article, I argue that the epistemic status of propositions of mixed mathematics is that of matters…
"Table 8" of "Measurement of multi-jet cross sections in proton-proton collisions at a 7 TeV center-of-mass energy"
2014
Differential cross section as a function of the scalar sum of the jet PTs (HT) for events with jet multiplicity >= 3.
"Table 9" of "Measurement of multi-jet cross sections in proton-proton collisions at a 7 TeV center-of-mass energy"
2014
Differential cross section as a function of the scalar sum of the jet PTs (HT) for events with jet multiplicity >= 4.
"Table 7" of "Measurement of multi-jet cross sections in proton-proton collisions at a 7 TeV center-of-mass energy"
2014
Differential cross section as a function of the scalar sum of the jet PTs (HT) for events with jet multiplicity >= 2.
"Table 6" of "Final COMPASS results on the deuteron spin-dependent structure function $g_1^{\rm d}$ and the Bjorken sum rule"
2017
Normalisations of the different data sets used in the QCD fit.
The double-incompleteness theorem
1976
Let T be a strong enough theory, and M - its metatheory, both are consistent. Then there is a closed arithmetical formula H that is undecidable in T, but one cannot prove in M neither that H is T-unprovable, nor that H is T-unrefutable. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
Deciding properties of integral relational automata
1994
This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL*+, which includes all ”linear time” formulae.
Minimal Büchi Automata for Certain Classes of LTL Formulas
2009
In this paper we calculate the minimal number of states of Buchi automata which encode some classes of linear temporal logic (LTL) formulas that are frequently used in model checking. Our results may be used for verification of the quality of algorithms which automatically translate LTL formulas into Buchi automata and for improving the quality and speed of such translators. In the last section of this paper we compare our lower-bound estimations to Buchi automata generated by two currently used translators: LTL2BA and SPOT.
Verification of scope-dependent hierarchical state machines
2008
AbstractA hierarchical state machine (Hsm) is a finite state machine where a vertex can either expand to another hierarchical state machine (box) or be a basic vertex (node). Each node is labeled with atomic propositions. We study an extension of such model which allows atomic propositions to label also boxes (Shsm). We show that Shsms can be exponentially more succinct than Shsms and verification is in general harder by an exponential factor. We carefully establish the computational complexity of reachability, cycle detection, and model checking against general Ltl and Ctl specifications. We also discuss some natural and interesting restrictions of the considered problems for which we can …