1,720,991 research outputs found
Continuous-Time Probabilistic KLAIM
No full textThe design of languages supporting network programming is a necessary step towards the formalisation of distributed and mobile computing. The existence of an abstract semantic framework constitutes the basis for a formal analysis of such systems. The KLAIM paradigm [5] provides such a semantic framework by introducing basic concepts and primitives addressing the key aspects of the coordination of interacting located processes. We extend this basic paradigm with probabilistic constructs with the aim of introducing a semantic basis for a quantitative analysis of networks
Operator Algebras and the Operational Semantics of Probabilistic Languages
No full textAbstractWe investigate the construction of linear operators representing the semantics of probabilistic programming languages expressed via probabilistic transition systems. Finite transition relations, corresponding to finite automata, can easily be represented by finite dimensional matrices; for the infinite case we need to consider an appropriate generalisation of matrix algebras. We argue that C*-algebras, or more precisely Approximately Finite (or AF) algebras, provide a sufficiently rich mathematical structure for modelling probabilistic processes.We show how to construct for a given probabilistic language a unique AF algebra A and how to represent the operational semantics of processes within this framework: finite computations correspond directly to operators in A, while infinite processes are represented by elements in the so-called strong closure of this algebra
Probabilistic Analysis of Programs: A Weak Limit Approach
Full text link25/06/14 meb. ok to add author retained copyright at time of conference
On Probabilistic Techniques for Data Flow Analysis
No full textAbstractWe present a semantics-based technique for analysing probabilistic properties of imperative programs. This consists in a probabilistic version of classical data flow analysis. We apply this technique to pWhile programs, i.e programs written in a probabilistic version of a simple While language. As a first step we introduce a syntax based definition of a linear operator semantics (LOS) which is equivalent to the standard structural operational semantics of While. The LOS of a pWhile program can be seen as the generator of a Discrete Time Markov Chain and plays a similar role as a collecting or trace semantics for classical While. Probabilistic Abstract Interpretation techniques are then employed in order to define data flow analyses for properties like Parity and Live Variables
Analysing Approximate Confinement under Uniform Attacks
No full textWe are concerned to give certain guarantees about the security of a system. We identify two kinds of attack: the internally scheduled attack (exemplified by Trojan Horse attacks) and externally scheduled attacks (exemplified by timing attacks). In this paper we focus on the latter. We present a semantic framework for studying such attacks in the context of PCCP, a simple process algebra with a constraint store. We show that a measure of the efficacy of an attacker can be determined by considering its observable behaviour over the ” average” store of the system (for some number of steps). We show how to construct an analysis to determine the average store using the technique of probabilistic abstract interpretation
Probabilistic Confinement in a Declarative Framework
No full textAbstractWe show how to formulate and analyse some security notions in the context of declarative programming. We concentrate on a particular class of security properties, namely the so-called confinement properties. Our reference language is concurrent constraint programming. We use a probabilistic version of this language (PCCP) to highlight via simple program examples the difference between probabilistic and nondeterministic confinement. The different role played by variables in imperative and constraint programming hinders a direct translation of the notion of confinement into our declarative setting. Therefore, we introduce the notion of identity confinement which is more appropriate for constraint languages. Finally, we present an approximating probabilistic semantics which can be used as a base for the analysis of confinement properties, and show its correctness with respect to the operational semantics of PCCP
Semantic abstraction and quantum computation
No full textWe present a logico-algebraic approach to probabilistic abstract interpretation based on the ortholattice structure of the projective measurement operators in quantum mechanics. On this base, we present a novel interpretation of quantum measurement as a probabilistic abstraction showing that the measurement of a physical observable essentially corresponds to a static analysis of the observed property
Linear Structures for Concurrency in Probabilistic Programming Languages
No full textWe introduce a semantical model based on operator algebras and we show the suitability of this model to capture both a quantitative version of non-determinism (in the form of a probabilistic choice) and concurrency. We present the model by referring to a generic language which generalises various probabilistic concurrent languages from different programming paradigms. We discuss the relation between concurrency and the commutativity of the resulting semantical domain. In particular, we use Gelfand's representation theorem to relate the semantical models of synchronisation-free and fully concurrent versions of the language. A central aspect of the model we present is that it allows for a unified view of both operational and denotational semantics for a concurrent language
- …
