2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ There is such a thing as a production rule: en.wikipedia.org/wiki/Production_(computer_science) though it does go in the opposite direction that you suggest. $\endgroup$
    – cody
    Commented Jan 17, 2019 at 14:28
  • 3
    $\begingroup$ You're more or less describing a Regular Grammar: en.wikipedia.org/wiki/Regular_grammar $\endgroup$
    – Denis
    Commented Jan 17, 2019 at 15:40
  • $\begingroup$ My idea is to extend the question little by little to see if this could be extended to turing machines, for instance $\endgroup$
    – user1868607
    Commented Jan 18, 2019 at 22:05
  • $\begingroup$ 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. $\endgroup$
    – Hermann Gruber
    Commented Jan 20, 2019 at 20:08
  • $\begingroup$ in some sense this would reflect duality memory-time $\endgroup$
    – user1868607
    Commented Feb 3, 2019 at 18:18

1 Answer 1

Reset to default
1
$\begingroup$

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", 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 (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. 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. In: Bachmair L. (eds) Rewriting Techniques and Applications. RTA 2000. Lecture Notes in Computer Science, vol 1833. Springer, Berlin, Heidelberg

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.