I have to implement algorithm, where definitions, input and output of program go as follows:
$Σ$ - finite, non-empty alphabet
A translation in $Z^2$ by vector $u = ( u_x , u_y ) ∈ Z^2$ will be denoted by $τ_u$ ,
$τ_ u : Z^ 2 ∋ ( x, y ) → ( x + u_x , y + u _y ) ∈ Z ^2 .$
Definition 1 (Directed Figure): Let $D\subset Z^2$be finite and connected, $b,e\in D$, $b,e$ don't necessary have label, and $l:D→Σ$ . A quadruple$f = (D, b, e, l)$ is called a directed figure (over $Σ$) with:
domain $dom (f) = D$ ,
start point begin $(f) = b$,
end point $end(f)= e$,
labelling function $label(f)= l$.
Example of Directed Figure:
$( [ (0 , 0) , (1 , 0) , (1 , 1) ] , (0 , 0) , (1 , 2) , [ (0 , 0) → a, (1 , 0) → b, (1 , 1) → c ] )$
The set of all directed figures over $Σ$ is denoted by $Σ^⋄$
Definition 2 (Catenation): Let $x= (D_x, b_x, e_x, l_x)$ and $y= (D_y, b_y, e_y, l_y)$be directed figures. Catenation of $x$ and $y$ with respect to mamerging function $m: Σ×Σ→Σ$ is defined as $x◦_m y = (D_x∪τ_{x_e−y_b}(D_y), b_x, τ_{x_e−y_b}(e_y), l)$
where
$l(z) = l_x(z)$ for $z∈D_x \setminus τ_{x_e−y_b}(D_y)$,
$l(z) = τ_{x_e−y_b}(l_y)(z)$ for $ z∈τ_{x_e−y_b}(D_y)\setminus D_x$,
$l(z) = m(l_x(z), τ_{x_e−y_b}(l_y)(z))$ for $z∈D_x∩τ_{x_e−y_b}(D_y).$
Definition 3 (Code) $X ⊆ Σ {^⋄_ m}$ is a code if for any $x _1 , . . . , x _k , y _1 , . . . , y _l ∈ X$ the equality $x_ 1 ◦_ m . . . ◦_ m x_k = y_ 1 ◦_ m . . . ◦_ m y_ l$ implies $k = l$ and $x_ i = y_ i$ for each i $∈{ 1 , . . . , k }$ .
Input:
- Code,
- Catenation of $x_1,x_2,\dots,x_n$ with respect to a merging function, where $x_1,x_2,\dots,x_n$ belong to a code (uniquely decodable)
- merging function $m : Σ × Σ → Σ$
Output: $x_1,x_2,\dots,x_n$
The definitions of directed figure, catenation, and code are in the paper from https://dmtcs.episciences.org/455/pdf by Michal Kolarz and Wlodzimierz Moczurad. (pages 3,4,5, respectively)
My first task was to implement a catenation of directed figures which was easy, now I have to do similar problem, but backwards. I thought about this problem for two days, but nothing really comes to my mind. I had a few ideas but when I've thought about them deeper, they had some flaws in them. Any ideas about how this algorithms should look like would be appreciated.
