Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn Stochastic Rewriting and Combinatorics via Rule-Algebraic Methods
149
0
0.0
(
0
)
Added by
EPTCS
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Nicolas Behr
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
For $beta > 1$ a real algebraic integer ({it the base}), the finite alphabets $mathcal{A} subset mathbb{Z}$ which realize the identity $mathbb{Q}(beta) = {rm Per}_{mathcal{A}}(beta)$, where ${rm Per}_{mathcal{A}}(beta)$ is the set of complex numbers which are $(beta, mathcal{A})$-eventually periodic representations, are investigated. Comparing with the greedy algorithm, minimal and natural alphabets are defined. The natural alphabets are shown to be correlated to the asymptotics of the Pierce numbers of the base $beta$ and Lehmers problem. The notion of rewriting trail is introduced to construct intermediate alphabets associated with small polynomial values of the base. Consequences on the representations of neighbourhoods of the origin in $mathbb{Q}(beta)$, generalizing Schmidts theorem related to Pisot numbers, are investigated. Applications to Galois conjugation are given for convergent sequences of bases $gamma_s := gamma_{n, m_1 , ldots , m_s}$ such that $gamma_{s}^{-1}$ is the unique root in $(0,1)$ of an almost Newman polynomial of the type $-1+x+x^n +x^{m_1}+ldots+ x^{m_s}$, $n geq 3$, $s geq 1$, $m_1 - n geq n-1$, $m_{q+1}-m_q geq n-1$ for all $q geq 1$. For $beta > 1$ a reciprocal algebraic integer close to one, the poles of modulus $< 1$ of the dynamical zeta function of the $beta$-shift $zeta_{beta}(z)$ are shown, under some assumptions, to be zeroes of the minimal polynomial of $beta$.
We obtain a necessary and sufficient condition for the linear independence of solutions of differential equations for hyperlogarithms. The key fact is that the multiplier (i.e. the factor $M$ in the differential equation $dS=MS$) has only singularities of first order (Fuchsian-type equations) and this implies that they freely span a space which contains no primitive. We give direct applications where we extend the property of linear independence to the largest known ring of coefficients.
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.
Convergent rewriting systems on algebraic structures give methods to solve decision problems, to prove coherence results, and to compute homological invariants. These methods are based on higher-dimensional extensions of the critical branching lemma that characterizes local confluence from confluence of the critical branchings. The analysis of local confluence of rewriting systems on algebraic structures, such as groups or linear algebras, is complicated because of the underlying algebraic axioms, and in some situations, local confluence properties require additional termination conditions. This article introduces the structure of algebraic polygraph modulo that formalizes the interaction between the rules of an algebraic rewriting system and the inherent algebraic axioms, and we show a critical branching lemma for algebraic polygraphs. We deduce from this result a critical branching lemma for rewriting systems on algebraic objects whose axioms are specified by convergent modulo rewriting systems. We illustrate our constructions for string, linear, and group rewriting systems.
This volume contains the formal proceedings of the 4th International Workshop on Rewriting Techniques for Program Transformations and Evaluation (WPTE 2017), held on 8th September 2017 in Oxford, United Kingdom, and affiliated with the Second International Conference on Formal Structures for Computation and Deduction (FSCD 2017).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
