اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدProbabilistic Rewriting and Asymptotic Behaviour: on Termination and Unique Normal Forms
144
0
0.0
(
0
)
تأليف
Claudia Faggian
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 ty
pes 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 syst
em 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
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
