Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [term-rewriting-systems]

The tag has no usage guidance.

37 questions
Filter by
Sorted by
Tagged with
77 views

### Time Complexity of KnuthBendixCompletion Algorithm [closed]

I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules ...
• 21
73 views

### Is there such a thing as "transformational semantics"?

The Wikipedia article about programming language semantics distinguishes three major approaches to semantics: denotational, operational, and axiomatic. What is the approach called when the meaning of ...
• 354
136 views

### Commutative operation benefits

With an associative operation I can rewrite a computation tree + / \ + 4 / \ + 3 / \ + 2 / \ 0 1 to be more efficient ...
• 71
243 views

### A clear and rigorous explanation of critical pairs and the Knuth-Bendix completion algorithm?

I'm looking for an explanation of critical pairs and the Knuth-Bendix completion algorithm that is at once rigorous and of high pedagogical value, i.e. clear, detailed, containing illustrative ...
• 354
140 views

• 14.5k
156 views

### Lengths and substitution in L-systems

Am looking into writing up a Lindenmayer systems implementation. I've looked at a few example implementations and the one thing that's giving me trouble at this stage is how symbols and substitutions ...
• 111
335 views

### A simple inference in rewriting theory

I was puzzled by a seeming simple inference in rewriting theory: if $y_1 \overset{*}{\leftarrow} x \overset{*}{\rightarrow} y_2$ then $y_1 \overset{*}{\leftrightarrow} y_2$. I don't understand how ...
• 2,805