The rewriting-systems tag has no wiki summary.
1
vote
2answers
49 views
Proving non-confluency and adding an equation to make it confluent and terminating
I currently have a system that has {f(a) = b, f(f(x)) = x} (part of an exam question - look at page 5 - exercise 1).
To start off with proving non-confluency, I am ...
2
votes
1answer
66 views
Example of a parsing/rewriting system?
I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually ...
4
votes
2answers
147 views
The meaning of modulo in “formula modulo a background theory”
I have been reading some papers where I keep reading stuff like “first-order formula modulo a background theory”. Does anyone know what modulo means in this case ? Is it something like “with respect ...
7
votes
1answer
199 views
Reduction rule for IF?
I'm working through Simon Peyton Jones' "The Implementation of Functional Programming Languages" and on page 20 I see:
IF TRUE ((λp.p) 3) ↔ IF TRUE 3 (per β red) (1)
...
8
votes
2answers
159 views
Confluence proof for a simple rewriting system
Assume we have a simple language that consists of the terms:
$\mathtt{true}$
$\mathtt{false}$
if $t_1,t_2,t_3$ are terms then so is $\mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$
...
7
votes
1answer
61 views
Is it possible to derive a string in this rewriting system?
Rewriting system is a set of rules in the form of $A \leftrightarrow B$.
If we apply that rule to a string $w$ we replace any substring $A$ in $w$ with a substring $B$ and vice versa.
Given a ...
