# Rewrite relations - proof of correctness

Let $$T \subseteq \Sigma^* \times \Sigma^*$$ be a regular relation. We define the obligatory rewrite relation over $$T$$ as follows: $$R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*$$ $$N(T) := Id(\Sigma^* \setminus (\Sigma^* \cdot dom(T) \cdot \Sigma^*)) \cup \{ \langle \epsilon, \epsilon \rangle \}$$ $$N(T)$$ is the identity relation of the set of all words that don't contain an infix in $$dom(T)$$ including the pair $$\langle \epsilon, \epsilon \rangle$$.

The idea is the following - we have an input string $$t \in \Sigma^*$$ and $$R^{obl}(T)(t)$$ will result in the translation of the substrings of $$t$$ which $$\in dom(T)$$ via $$Т$$, and the ones $$\notin dom(T)$$ via identity.

Example 1: $$T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}$$, the input text $$t = babacbca$$ is decomposed as $$t = b \cdot ab \cdot ac \cdot bc \cdot a$$ and the substrings $$\{ b,ac,a \} \subseteq dom(N(T))$$, whereas, $$\{ab, bc\} \subseteq dom(T)$$. So $$R^{obl}(T)(t) = b \cdot d \cdot ac \cdot d \cdot a = bdacda$$

Example 2: $$T = \{ \langle ab, d \rangle, \langle bc, d \rangle \}, t = abcc$$. This time we have two possible decompositions due to overlapping. $$t = ab \cdot cc = a \cdot bc \cdot c$$, therefore, two possible translations $$\langle abcc, dcc \rangle \in R^{obl}(T), \langle abcc, adc \rangle \in R^{obl}(T)$$.

My questions is - how do we formulate a proof of correctness for such a construction? That it indeed translates the words as described

A bit of a context. I've studying rewrite systems based on regular relations (implemented as finite-state transducers) and more specifically the papers "Regular Models of Phonological Rule Systems" by Kaplan & Kay (1994) and "Directed Replacement" by Karttunnen (1996). They construct complex rewrite relations by using only the regular set and relation algebra, however, the papers do not provide formal proofs that their method is correct. If anyone has experience in this field and can provide some guidance, I'll greatly appreciate it.

• What is your definition of a regular relation? – J.-E. Pin Jul 30 at 7:15
• I use the definition from Kaplan & Kay (94). It is very similar to the definition of regular languages. 1. The empty set and { a } for all a in Sigma x Sigma are regular relations 2. If R1, R2 and R are binary regular relations, then so are 2.1 R1 . R2 = { xy | x in R1, y in R2 } 2.2 R1 union R2 2.3 R* (2-way Kleene closure) 2.4 There are no other regular relations In literature you can find the equivalent term "rational relations" to be used. – Denis Kyashif Jul 31 at 8:03

To simplify, let $$D$$ be the domain of $$T$$ and let $$R = \{\epsilon\} \cup (\Sigma^* \setminus \Sigma^*D\Sigma^*)$$. Then by definition $$N(T) = Id_R \quad \text{and} \quad R^{obl}(T) = N(T)(TN(T))^*.$$ Here is a formal way to justify your idea. Let $$(u,v) \in \Sigma^* \times \Sigma^*$$. By definition, $$(u,v) \in R^{obl}(T)$$ if and only if $$(u,v)$$ can be written as $$(u, v) = (r_0, r_0)(u_1, v_1)(r_1, r_1)(u_2,v_2) \dotsm (r_{k-1}, r_{k-1})(u_k,v_k)(r_k, r_k)$$ where $$r_0, r_1, \ldots, r_k \in R$$ and $$(u_1, v_1), \ldots, (u_k,v_k) \in T$$, which is exactly what you describe in your sentence starting by "The idea is the following".