0
$\begingroup$

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:

  1. Code,
  2. 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)
  3. 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.

$\endgroup$
  • $\begingroup$ Given that it is non-trivial to determine whether your setup is uniquely decodable, I suspect that the problem is somewhat difficult, and you might have to use ideas from the paper. I think this question is a bit too elaborate for this site, but perhaps someone else will be willing to help you with your homework. $\endgroup$ – Yuval Filmus Aug 7 '17 at 16:23
  • $\begingroup$ I've forgot to put the definition of Code . My setup is uniquely decodable, I will add this information. $\endgroup$ – Michał Aug 7 '17 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.