• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Stochastic mechanics of graph rewriting
【24h】

Stochastic mechanics of graph rewriting

机译：图重写的随机力学

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We propose an algebraic approach to stochastic graph-rewriting which extends the classical construction of the Heisenberg-Weyl algebra and its canonical representation on the Fock space. Rules are seen as particular elements of an algebra of “diagrams”: the diagram algebra D. Diagrams can be thought of as formal computational traces represented in partial time. They can be evaluated to normal diagrams (each corresponding to a rule) and generate an associative unital non-commutative algebra of rules: the rule algebra D. Evaluation becomes a morphism of unital associative algebras which maps general diagrams in D to normal ones in R. In this algebraic reformulation, usual distinctions between graph observables (real-valued maps on the set of graphs defined by counting subgraphs) and rules disappear. Instead, natural algebraic substructures of R arise: formal observables are seen as rules with equal left and right hand sides and form a commutative subalgebra, the ones counting subgraphs forming a sub-subalgebra of identity rules. Actual graph-rewriting is recovered as a canonical representation of the rule algebra as linear operators over the vector space generated by (isomorphism classes of) finite graphs. The construction of the representation is in close analogy with and subsumes the classical (multi-type bosonic) Fock space representation of the HeisenbergWeyl algebra. This shift of point of view, away from its canonical representation to the rule algebra itself, has unexpected consequences. We find that natural variants of the evaluation morphism map give rise to concepts of graph transformations hitherto not considered. These will be described in a separate paper [2]. In this extended abstract we limit ourselves to the simplest concept of double-pushout rewriting (DPO). We establish “jump-closure”, i.e. that the subspace of representations of formal graph observables is closed under the action of any rule set. It follows that for any rule set, one can derive a formal and self-consistent Kolmogorov backward equation for (representations of) formal observables.
机译：我们提出了一种用于随机图形重写的代数方法，该方法扩展了Heisenberg-Weyl代数的经典构造及其在Fock空间上的典范表示。规则被视为“图”的代数的特定元素：图的代数D。图可被视为部分时间内表示的形式化计算轨迹。可以将它们评估为法线图（每个都对应于一条规则），并生成一个规则的联合单位非交换代数：规则代数D。求值成为单位联合代数的一种形态，它将D中的一般图映射到R中的普通图。在这种代数形式中，图可观测值（通过计数子图定义的图集上的实值图）与规则之间的通常区别消失了。取而代之的是，出现了R的自然代数子结构：形式可观察物被看作是左右手边相等的规则，并形成可交换的子代数，计算子图的子可数构成恒等子规则的子子代数。实际的图形重写被恢复为规则代数的典范表示形式，即作为由有限图（的同构类）生成的向量空间上的线性算子。表示的构造与HeisenbergWeyl代数的经典（多类型玻色子）Fock空间表示非常相似，并且将其包含在内。这种观点的转变，从其规范的表示形式转移到规则代数本身，产生了意想不到的后果。我们发现评估态射图的自然变体引起了迄今为止尚未考虑的图变换的概念。这些将在另一篇论文中描述[2]。在这个扩展的摘要中，我们将自己限制在最简单的双重推送重写（DPO）概念上。我们建立“跳跃关闭”，即形式图可观察值表示的子空间在任何规则集的作用下被关闭。由此可见，对于任何规则集，都可以为形式可观测量（表示形式）导出形式上和自洽的Kolmogorov向后方程。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号