Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProbabilistic Rewriting and Asymptotic Behaviour: on Termination and Unique Normal Forms
144
0
0.0
(
0
)
Added by
Claudia Faggian
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Authors
Claudia Faggian
Ask ChatGPT about the research
No Arabic abstract
While a mature body of work supports the study of rewriting systems, abstract tools for Probabilistic Rewriting are still limited. In this paper we study the question of emph{uniqueness of the result} (unique limit distribution), and develop a set of proof techniques to analyze and compare emph{reduction strategies}. The goal is to have tools to support the emph{operational} analysis of emph{probabilistic} calculi (such as probabilistic lambda-calculi) whose evaluation is also non-deterministic, in the sense that different reductions are possible.
rate research
Read More
Extending our own and others earlier approaches to reasoning about termination of probabilistic programs, we propose and prove a new rule for termination with probability one, also known as almost-certain termination. The rule uses both (non-strict) super martingales and guarantees of progress, together, and it seems to cover significant cases that earlier methods do not. In particular, it suffices for termination of the unbounded symmetric random walk in both one- and two dimensions: for the first, we give a proof; for the second, we use a theorem of Foster to argue that a proof exists. Non-determinism (i.e. demonic choice) is supported; but we do currently restrict to discrete distributions.
We present a reduction of the termination problem for a Turing machine (in the simplified form of the Post correspondence problem) to the problem of determining whether a continuous-time Markov chain presented as a set of Kappa graph-rewriting rules has an equilibrium. It follows that the problem of whether a computable CTMC is dissipative (ie does not have an equilibrium) is undecidable.
Building upon the rule-algebraic stochastic mechanics framework, we present new results on the relationship of stochastic rewriting systems described in terms of continuous-time Markov chains, their embedded discrete-time Markov chains and certain types of generating function expressions in combinatorics. We introduce a number of generating function techniques that permit a novel form of static analysis for rewriting systems based upon marginalizing distributions over the states of the rewriting systems via pattern-counting observables.
We discuss the history of the monodromy theorem, starting from Weierstrass, and the concept of monodromy group. From this viewpoint we compare then the Weierstrass , the Legendre and other normal forms for elliptic curves, explaining their geometric meaning and distinguishing them by their stabilizer in P SL(2,Z) and their monodromy. Then we focus on the birth of the concept of the Jacobian variety, and the geometrization of the theory of Abelian functions and integrals. We end illustrating the methods of complex analysis in the simplest issue, the difference equation $f(z) = g(z+1) - g(z)$ on $mathbb C$.
In this paper, we study how graph transformations based on sesqui-pushout rewriting can be reversed and how the composition of rewrites can be constructed. We illustrate how such reversibility and composition can be used to design an audit trail system for individual graphs and graph hierarchies. This provides us with a compact way to maintain the history of updates of an object, including its multip
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
