<?xml version="1.0" encoding="utf-8" standalone="yes"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom">
  <channel>
    <title>A Framework for Scalable Graph Rewriting on DPhil Thesis</title>
    <link>http://localhost:1313/04_rewriting/</link>
    <description>Recent content in A Framework for Scalable Graph Rewriting on DPhil Thesis</description>
    <generator>Hugo</generator>
    <language>en-gb</language>
    <atom:link href="http://localhost:1313/04_rewriting/index.xml" rel="self" type="application/rss+xml" />
    <item>
      <title>Overview</title>
      <link>http://localhost:1313/04_rewriting/01_overview/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/04_rewriting/01_overview/</guid>
      <description>&lt;p&gt;The framework we propose can be summarised by the diagram below.&#xA;It is composed of two main components: &lt;em&gt;pattern matching&lt;/em&gt;&#xA;is tasked with finding all possible applications of rewrite rules from&#xA;the set of pre-defined rules.&#xA;Importantly, for this computation, we introduce an offline pre-processing step&#xA;that builds a data structure that is amenable to pattern matching from the&#xA;supplied set of rewrite rules. This allows us to obtain significant speedups&#xA;in the exploration phase of the framework.&#xA;The design of the pattern matching engine is described in more detail&#xA;in &lt;span&gt;section &lt;/span&gt;&lt;a href=&#34;http://localhost:1313/04_rewriting/#sec:pattern&#34;&gt;4.2&lt;/a&gt;, while the original contributions&#xA;with a detailed presentation of the pre-processing computation and an analysis of the&#xA;asymptotic speedup are presented in &lt;span&gt;chapter &lt;/span&gt;&lt;a href=&#34;http://localhost:1313/05_matching/&#34;&gt;5&lt;/a&gt;.&lt;/p&gt;</description>
    </item>
    <item>
      <title>Pattern matching engine</title>
      <link>http://localhost:1313/04_rewriting/secpattern/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/04_rewriting/secpattern/</guid>
      <description>&lt;p&gt;As discussed in the &lt;a href=&#34;http://localhost:1313/03_compiler/#superoptimisation&#34;&gt;review of superoptimisation&lt;/a&gt;&#xA;(sec. &lt;a href=&#34;http://localhost:1313/03_compiler/#sec5&#34;&gt;3.5&lt;/a&gt;), the adaptation of the technique to&#xA;quantum computing benefits from the use of thousands of rewrite rules. However,&#xA;the performance reaches a ceiling as the number of rewrite rules grows, when&#xA;pattern matching becomes the bottleneck.&#xA;This was the main motivation for the work in &lt;span class=&#34;citation&#34;&gt;&lt;span data-bibtex-key=&#34;Mondada2024&#34; class=&#34;citation-key&#34;&gt;Mondada, 2024&lt;/span&gt;&lt;span class=&#34;citation-full&#34;&gt;&lt;span class=&#34;authors&#34;&gt;Luca  Mondada and Pablo  Andrés-Martínez&lt;/span&gt;. 2024. Scalable Pattern Matching in Computation Graphs. In &lt;em&gt;15th International Workshop on Graph Computation Models&lt;/em&gt;&lt;/span&gt;&lt;/span&gt;, which speeds up&#xA;pattern matching by introducing a pre-computed state automaton data structure.&#xA;The result is pattern matching in a runtime that is independent on the number&#xA;of rewrite rules being considered&amp;nbsp;&amp;ndash;&amp;nbsp;reaching a 20x speedup on datasets of&#xA;practical interest.&lt;/p&gt;</description>
    </item>
    <item>
      <title>Rewriting Strategies and Distributed Architecture</title>
      <link>http://localhost:1313/04_rewriting/secrewrite/</link>
      <pubDate>Mon, 01 Jan 0001 00:00:00 +0000</pubDate>
      <guid>http://localhost:1313/04_rewriting/secrewrite/</guid>
      <description></description>
    </item>
  </channel>
</rss>
