<p>As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in <em>term</em> rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree automata, that is, finite automata accepting trees instead of strings. I've heard that the following is a very good book on tree automata (although I haven't read through it yet).</p>

<p>H. Comon, M. Dauchet, R. Gilleron, C. Löding
and F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: "<a href="http://tata.gforge.inria.fr/" rel="nofollow noreferrer">Tree Automata: Techniques and Applications</a>", 2007.</p>

<p>As far as I can tell, the question you asked is quite natural and thus has already been explored. With some googling I found out that <a href="https://www.researchgate.net/profile/Sophie_Tison" rel="nofollow noreferrer">Sophie Tison</a> (co-author of the TATA book above) had some invited talks with "term rewriting" and "tree automata" in the title (I haven't read them either).</p>

<p>Tison S. (2011) <a href="https://doi.org/10.1007/978-3-642-21691-6_2" rel="nofollow noreferrer">Tree Automata, (Dis-)Equality Constraints and Term Rewriting</a>. In: Ong L. (eds) Typed Lambda Calculi and Applications. TLCA 2011. Lecture Notes in Computer Science, vol 6690. Springer, Berlin, Heidelberg</p>

<p>Tison S. (2000) <a href="https://doi.org/10.1007/10721975_2" rel="nofollow noreferrer">Tree Automata and Term Rewrite Systems</a>. In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg</p>

CC BY-SA 4.0
2019-01-20T19:50:47.707Z
2019-01-20T19:50:47.707Z
Hermann Gruber
<p>It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the <span class="math-container">$\epsilon$</span> word. In other words acceptance is just a particular case of equational reasoning in term rewriting systems.</p>

<p>My question is, has this approach been developed before? In particular, it would be  interesting to see  if Turing machines can be modelled in this language.</p>

<p><strong>Comments</strong></p>

<p>Someone has suggested regular grammars do model deterministic automata. Maybe it is useful to recall the difference between abstract reduction system and term rewriting system. From "Term rewriting and all that":</p>

<blockquote>
  <p>A rewrite rule is an identity <span class="math-container">$l \approx r$</span> such that l i not a variable and <span class="math-container">$Var(l) \supseteq Var(r)$</span>. In this case we may write <span class="math-container">$l \to r$</span>. A term rewriting system is a set of rewrite rules.</p>
</blockquote>

<p>It seems that formal gramars fit better the definition of abstract reduction system:</p>

<blockquote>
  <p>An abstract reduction system is a pair <span class="math-container">$(A,\to)$</span> where the reduction <span class="math-container">$\to$</span> is a binary relation on the set <span class="math-container">$A$</span>, i.e. <span class="math-container">$\to \subseteq A \times A$</span>.</p>
</blockquote>

<p>For the future I note:</p>

<p><a href="https://cstheory.stackexchange.com/questions/625/relationship-between-turing-machine-and-lambda-calculus">Relationship between Turing Machine and Lambda calculus?</a></p>

CC BY-SA 4.0
2019-01-17T14:28:20.440Z
There is such a thing as a production rule: https://en.wikipedia.org/wiki/Production_(computer_science) though it does go in the opposite direction that you suggest.
cody
CC BY-SA 4.0
2019-01-17T15:40:41.487Z
You're more or less describing a Regular Grammar: https://en.wikipedia.org/wiki/Regular_grammar
Denis
CC BY-SA 4.0
2019-01-18T22:05:52.313Z
My idea is to extend the question little by little to see if this could be extended to turing machines, for instance
user1868607
CC BY-SA 4.0
2019-01-20T20:08:29.920Z
Uhm, please refrain from extending your question little by little. If you have multiple (research-level) questions, please post multiple questions. From my experience, the people in this forum are very friendly and generous, but most of them don't have time for engaging in conversations/discussions. Consequently, the format of TCS-stackexchange is precisely Q&A and not something else.
Hermann Gruber
CC BY-SA 4.0
2019-02-03T18:18:33.157Z
in some sense this would reflect duality memory-time
user1868607
<reference-request><automata-theory><term-rewriting-systems>
Automata as term rewriting systems
user1868607
# Automata as term rewriting systems

(Asked by: username_0 on 2019-01-17)

It came to my mind that automata (say to start DFA) can be thought as a special kind of rewriting systems. So if one has a word w , one tries to reduce it to the $\epsilon$ word. In other words acceptance is just a particular case of equational reasoning in term rewriting systems.

My question is, has this approach been developed before? In particular, it would be interesting to see if Turing machines can be modelled in this language.

**Comments**

Someone has suggested regular grammars do model deterministic automata. Maybe it is useful to recall the difference between abstract reduction system and term rewriting system. From "Term rewriting and all that":

> A rewrite rule is an identity $l \approx r$ such that l i not a variable and $Var(l) \supseteq Var(r)$. In this case we may write $l \to r$. A term rewriting system is a set of rewrite rules.

It seems that formal gramars fit better the definition of abstract reduction system:

> An abstract reduction system is a pair $(A,\to)$ where the reduction $\to$ is a binary relation on the set $A$, i.e. $\to \subseteq A \times A$.

For the future I note:

[Relationship between Turing Machine and Lambda calculus?](https://cstheory.stackexchange.com/questions/625/relationship-between-turing-machine-and-lambda-calculus)

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

> **Comments:**
> **username_1**: There is such a thing as a production rule: https://en.wikipedia.org/wiki/Production_(computer_science) though it does go in the opposite direction that you suggest.  
> **username_2**: You're more or less describing a Regular Grammar: https://en.wikipedia.org/wiki/Regular_grammar  
> **username_0**: My idea is to extend the question little by little to see if this could be extended to turing machines, for instance  
> **username_3**: Uhm, please refrain from extending your question little by little. If you have multiple (research-level) questions, please post multiple questions. From my experience, the people in this forum are very friendly and generous, but most of them don't have time for engaging in conversations/discussions. Consequently, the format of TCS-stackexchange is precisely Q&A and not something else.  
> **username_0**: in some sense this would reflect duality memory-time  

---

## 1 answers

### Answer by username_3 on 2019-01-20. Score: 1 | Accepted answer

As mentioned in the comments, regular grammars are more or less a (string) rewriting system, where the arrow of a derivation is in the reverse direction of the rewriting arrow. Since you seem to be especially interested in *term* rewriting systems (as opposed to string rewriting systems), the automaton model that you are probably looking for is that of tree automata, that is, finite automata accepting trees instead of strings. I've heard that the following is a very good book on tree automata (although I haven't read through it yet).

H. Comon, M. Dauchet, R. Gilleron, C. Löding
and F. Jacquemard, D. Lugiez, S. Tison and M. Tommasi: "[Tree Automata: Techniques and Applications](http://tata.gforge.inria.fr/)", 2007.

As far as I can tell, the question you asked is quite natural and thus has already been explored. With some googling I found out that [Sophie Tison](https://www.researchgate.net/profile/Sophie_Tison) (co-author of the TATA book above) had some invited talks with "term rewriting" and "tree automata" in the title (I haven't read them either).

Tison S. (2011) [Tree Automata, (Dis-)Equality Constraints and Term Rewriting](https://doi.org/10.1007/978-3-642-21691-6_2). In: Ong L. (eds) Typed Lambda Calculi and Applications. TLCA 2011. Lecture Notes in Computer Science, vol 6690. Springer, Berlin, Heidelberg

Tison S. (2000) [Tree Automata and Term Rewrite Systems](https://doi.org/10.1007/10721975_2). In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg


---

