Search results for "Logic in computer science"
showing 10 items of 129 documents
The Fluted Fragment with Transitivity
2019
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive relation is available. On the other hand we show that the satisfiability problem is undecidable already for the two-variable fragment of the logic in the presence of three transitive relations.
The Inconsistent Labelling Problem of Stutter-Preserving Partial-Order Reduction
2020
AbstractIn model checking, partial-order reduction (POR) is an effective technique to reduce the size of the state space. Stubborn sets are an established variant of POR and have seen many applications over the past 31 years. One of the early works on stubborn sets shows that a combination of several conditions on the reduction is sufficient to preserve stutter-trace equivalence, making stubborn sets suitable for model checking of linear-time properties. In this paper, we identify a flaw in the reasoning and show with a counter-example that stutter-trace equivalence is not necessarily preserved. We propose a solution together with an updated correctness proof. Furthermore, we analyse in whi…
Complete Graphical Language for Hermiticity-Preserving Superoperators
2023
Universal and complete graphical languages have been successfully designed for pure state quantum mechanics, corresponding to linear maps between Hilbert spaces, and mixed states quantum mechanics, corresponding to completely positive superoperators. In this paper, we go one step further and present a universal and complete graphical language for Hermiticity-preserving superoperators. Such a language opens the possibility of diagrammatic compositional investigations of antilinear transformations featured in various physical situations, such as the Choi-Jamio{\l}kowski isomorphism, spin-flip, or entanglement witnesses. Our construction relies on an extension of the ZW-calculus exhibiting a n…
The minimal probabilistic and quantum finite automata recognizing uncountably many languages with fixed cutpoints
2019
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Automata, Logic and Semantics ; 1365-8050
Foundations for the formalization of metamathematics and axiomatizations of consequence theories
2004
Abstract This paper deals with Tarski's first axiomatic presentations of the syntax of deductive system. Andrzej Grzegorczyk's significant results which laid the foundations for the formalization of metalogic, are touched upon briefly. The results relate to Tarski's theory of concatenation, also called the theory of strings, and to Tarski's ideas on the formalization of metamathematics. There is a short mention of author's research in the field. The main part of the paper surveys research on the theory of deductive systems initiated by Tarski, in particular research on (i) the axiomatization of the general notion of consequence operation, (ii) axiom systems for the theories of classic conse…
Mathematical logic and quantum finite state automata
2009
AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
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.
Connecting Granular and Topological Relations through Description Logics
2021
Granularity deals with organizing in greater or lesser detail data, information, and knowledge that resides at a granular level. This organization is carried out according to certain criteria, which thereby provide a context view or dimension also called granular perspective. Topological relations express spatial associations among geospatial features (points, polylines, and polygons); they represent a horizontal spatial analysis. The two domains allow scientists to conceive different perspectives of the world. In this article, we aim to combine the two representations through Description Logics (DL) rules to relate granular (vertical representation) and geospatial topological (horizontal r…
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.