<p>I'm not sure this really answers your question, but you might be interested in this paper: <a href="https://lmcs.episciences.org/10963" rel="nofollow noreferrer">https://lmcs.episciences.org/10963</a></p>
<p>It gives a graphical language of string diagrams such that:</p>
<ul>
<li>the usual drawing of an NFA as a graph can be translated into a string diagram whose picture looks very similar;</li>
<li>there is a finite set of equations on these diagrams, which can be seen as rules for local graph rewriting (except they can be used &quot;in both directions&quot;), that completely characterize equivalence of automata (in the sense of recognizing the same language).</li>
</ul>

CC BY-SA 4.0
2024-12-11T21:38:52.780Z
2024-12-11T21:38:52.780Z
Lê Thành Dũng 'Tito' Nguyễn
<p>Suppose one is designing an algorithm on finite-state automata that involves lot of transformations over their underlying graph.</p>
<p>A way of looking at it would be in the framework of graph rewriting. For example, I'm reading bit about algebraic graph rewriting, although term graph rewriting would do for my purposes as well. One of the things one may gain from such a viewpoint is an easier proof of termination.</p>
<p>However, in an algorithm that manipulates <em>automata</em> and not any kind of graph, one wants to also maintain other properties while performing the rewriting, for example:</p>
<ol>
<li>equivalence to the original automaton</li>
<li>determinism, if the original automaton was deterministic</li>
</ol>
<p>For example, I may be mistaken here, but it seems to me that the operation of cloning a node introduces nondeterminism but preserves equivalence. I'm looking for such kind of results and observations.</p>
<p>So has anybody studied what happens when one applies tools from algebraic graph rewriting or term graph rewriting to the graphs defining finite automata, i.e. which kind of rewritings preserve the above properties or other interesting automata-specific properties?</p>

<reference-request><graph-theory><automata-theory><term-rewriting-systems>
Transforming finite automata with graph rewriting
Nicola Gigante
# Transforming finite automata with graph rewriting

(Asked by: username_0 on 2024-09-23)

Suppose one is designing an algorithm on finite-state automata that involves lot of transformations over their underlying graph.

A way of looking at it would be in the framework of graph rewriting. For example, I'm reading bit about algebraic graph rewriting, although term graph rewriting would do for my purposes as well. One of the things one may gain from such a viewpoint is an easier proof of termination.

However, in an algorithm that manipulates *automata* and not any kind of graph, one wants to also maintain other properties while performing the rewriting, for example:

1. equivalence to the original automaton
2. determinism, if the original automaton was deterministic

For example, I may be mistaken here, but it seems to me that the operation of cloning a node introduces nondeterminism but preserves equivalence. I'm looking for such kind of results and observations.

So has anybody studied what happens when one applies tools from algebraic graph rewriting or term graph rewriting to the graphs defining finite automata, i.e. which kind of rewritings preserve the above properties or other interesting automata-specific properties?

**Tags:** reference-request, graph-theory, automata-theory, term-rewriting-systems


---

## 1 answers

### Answer by username_1 on 2024-12-11. Score: 4

I'm not sure this really answers your question, but you might be interested in this paper: <https://lmcs.episciences.org/10963>

It gives a graphical language of string diagrams such that:

* the usual drawing of an NFA as a graph can be translated into a string diagram whose picture looks very similar;
* there is a finite set of equations on these diagrams, which can be seen as rules for local graph rewriting (except they can be used "in both directions"), that completely characterize equivalence of automata (in the sense of recognizing the same language).


---

