1,721,021 research outputs found
Parity automata for quantitative linear time logics
Get PDFWe initiate a study of automata-based model checking for previously proposed quantitative linear time logics interpreted over coalgebras. Our results include: (i) an automata-theoretic characterisation of the semantics of these logics, based on a notion of extent of a quantitative parity automaton, (ii) a study of the expressive power of Büchi variants of such automata, with implications on the expressiveness of fragments of the logics considered, and (iii) a naïve algorithm for computing extents, under additional assumptions on the domain of truth values
Lattice-theoretic progress measures and coalgebraic model checking
Get PDFIn the context of formal verification in general and model checking in particular, parity games serve as a mighty vehicle: many problems are encoded as parity games, which are then solved by the seminal algorithm by Jurdzinski. In this paper we identify the essence of this workflow to be the notion of progress measure, and formalize it in general, possibly infinitary, lattice-theoretic terms. Our view on progress measures is that they are to nested/alternating fixed points what invariants are to safety/greatest fixed points, and what ranking functions are to liveness/least fixed points. That is, progress measures are combination of the latter two notions (invariant and ranking function) that have been extensively studied in the context of (program) verification. We then apply our theory of progress measures to a general model-checking framework, where systems are categorically presented as coalgebras. The framework's theoretical robustness is witnessed by a smooth transfer from the branching-time setting to the linear-time one. Although the framework can be used to derive some decision procedures for finite settings, we also expect the proposed framework to form a basis for sound proof methods for some undecidable/infinitary problems
Coalgebraic CTL: fixpoint characterization and polynomial-time model checking
No full textWe introduce a path-based coalgebraic temporal logic, CoalgebraicCTL (CCTL), as a categorical abstraction of standard ComputationTree Logic (CTL). Our logic can be used to formalize propertiesof systems modeled as coalgebras with branching. We present the syntaxand path-based semantics of CCTL, and show how to encode this logicinto a coalgebraic fixpoint logic with a step-wise semantics. Our mainresult shows that this encoding is semantics-preserving. We also presenta polynomial-time model-checking algorithm for CCTL, inspired by thestandard model-checking algorithm for CTL but described in categoricalterms. A key contribution of our paper is to identify the categoricalessence of the standard encoding of CTL into the modal mu-calculus.This categorical perspective also explains the absence of a similar encodingof PCTL (Probabilistic CTL) into the probabilistic mu-calculus
Automated Deductive Verification of Probabilistic Programs
Get PDFWe study both foundational and practical aspects of the automated deductive verification of discrete probabilistic programs. Our special emphasis is on the verification of possibly unbounded loops by quantitative loop invariants. We build upon Kozen's, McIver & Morgan's, and Kaminski's weakest preexpectation calculus for reasoning about expected outcomes such as the probability of terminating in some postcondition or the expected final value of a program variable. The weakest preexpectation calculus replaces predicates from classical program verification by more general expectations --- functions mapping program states to numbers instead of truth values. We study a syntax for specifying expectations, providing a foundation for automated deductive probabilistic program verifiers. We prove that our syntax is expressive and hence obtain a relatively complete verification system for reasoning about expected outcomes. We then present three different approaches for automating the verification of bounds on expected outcomes of linear loops, all of which combine weakest preexpectation reasoning with Satisfiability Modulo Theories (SMT) techniques: 1. We revisit two well-established verification techniques for transition systems, k-induction and bounded model checking (BMC), in the more general setting of bounding least fixpoints of functions over complete lattices, yielding latticed k-induction and latticed BMC. Instantiating our latticed techniques with the weakest preexpectation calculus enables the fully automatic verification of linear loops taken from the literature. 2. We present a counterexample-guided inductive synthesis approach for the synthesis of quantitative loop invariants. This enables the fully automatic verification of bounds on both expected outcomes and expected runtimes. Our implementation synthesizes quantitative invariants of various linear loops taken from the literature, can beat state-of-the-art probabilistic model checkers on finite-state programs, and is competitive with modern tools dedicated to invariant synthesis or expected runtime reasoning. 3. We present PrIC3 --- the first truly quantitative extension of the state-of-the-art qualitative symbolic model checking algorithm IC3 to symbolic model checking of Markov decision processes. By marrying PrIC3 with the weakest preexpectation calculus, we obtain a symbolic model checking algorithm for probabilistic programs. Alongside, we present an implementation of PrIC3 featuring IC3-specific techniques such as generalization
Automated deductive verification of probabilistic programs
No full textWe study both foundational and practical aspects of the automated deductive verification of discrete probabilistic programs. Our special emphasis is on the verification of possibly unbounded loops by quantitative loop invariants. We build upon Kozen's, McIver & Morgan's, and Kaminski's weakest preexpectation calculus for reasoning about expected outcomes such as the probability of terminating in some postcondition or the expected final value of a program variable. The weakest preexpectation calculus replaces predicates from classical program verification by more general expectations --- functions mapping program states to numbers instead of truth values. We study a syntax for specifying expectations, providing a foundation for automated deductive probabilistic program verifiers. We prove that our syntax is expressive and hence obtain a relatively complete verification system for reasoning about expected outcomes. We then present three different approaches for automating the verification of bounds on expected outcomes of linear loops, all of which combine weakest preexpectation reasoning with Satisfiability Modulo Theories (SMT) techniques: 1. We revisit two well-established verification techniques for transition systems, k-induction and bounded model checking (BMC), in the more general setting of bounding least fixpoints of functions over complete lattices, yielding latticed k-induction and latticed BMC. Instantiating our latticed techniques with the weakest preexpectation calculus enables the fully automatic verification of linear loops taken from the literature. 2. We present a counterexample-guided inductive synthesis approach for the synthesis of quantitative loop invariants. This enables the fully automatic verification of bounds on both expected outcomes and expected runtimes. Our implementation synthesizes quantitative invariants of various linear loops taken from the literature, can beat state-of-the-art probabilistic model checkers on finite-state programs, and is competitive with modern tools dedicated to invariant synthesis or expected runtime reasoning. 3. We present PrIC3 --- the first truly quantitative extension of the state-of-the-art qualitative symbolic model checking algorithm IC3 to symbolic model checking of Markov decision processes. By marrying PrIC3 with the weakest preexpectation calculus, we obtain a symbolic model checking algorithm for probabilistic programs. Alongside, we present an implementation of PrIC3 featuring IC3-specific techniques such as generalization
Mixed quantum states in higher categories
Get PDFThere are two ways to describe the interaction between classical and quantum information categorically: one based on completely positive maps between Frobenius algebras, the other using symmetric monoidal 2-categories. This paper makes a first step towards combining the two. The integrated approach allows a unified description of quantum teleportation and classical encryption in a single 2-category, as well as a universal security proof applicable simultaneously to both scenarios
Abstract structure of unitary oracles for quantum algorithms
No full textWe show that a pair of complementary dagger-Frobenius algebras, equipped with a self-conjugate comonoid homomorphism onto one of the algebras, produce a nontrivial unitary morphism on the product of the algebras. This gives an abstract understanding of the structure of an oracle in a quantum computation, and we apply this understanding to develop a new algorithm for the deterministic identification of group homomorphisms into abelian groups. We also discuss an application to the categorical theory of signal-flow networks
A 2-Categorical Analysis of Complementary Families, Quantum Key Distribution and the Mean King Problem
Get PDFThis paper explores the use of 2-categorical technology for describing and reasoning about complex quantum procedures. We give syntactic definitions of a family of complementary measurements, and of quantum key distribution, and show that they are equivalent. We then show abstractly that either structure gives a solution to the Mean King problem, which we also formulate 2-categorically
Going Beyond Counting First Authors in Author Co-citation Analysis
Get PDFThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
