JXPATH: nice jar from Apache Commons to evaluate XPATH over graph objects (i.e. JavaBeans).

HashCodeBuilder: another nice Apache Commons API to overwrite your Java hashcode() methods the-right-way (hope).

# Combinatwordsing on sunday…

From S. Tringali. link Let $\Sigma$ be a set and denote by $\Sigma^*$ the free monoid on $\Sigma$, which we write, as usual, in multiplicative notation. Let $\varepsilon$ be the identity element of $\Sigma^*$ and $|\cdot|$ the function $\Sigma^* \to \mathbb N$ mapping a word $w$ to its length (here, $\mathbb N$ means the non-negative integers). Then, pick $w \in \Sigma^+$.

1. Prove that for every $k \in \mathbb N$ there exists at most one pair $(e,v) \in \mathbb N \times \Xi^*$ such that $v^e = w$ and $|v| = k$.

2. Prove the following: If $v_1, v_2 \in \Xi^*$ and $e_1, e_2 \in \mathbb N^+$ are such that $v_1^{e_1} = v_2^{e_2} = w$, then there exists $v \in \Xi^*$ such that $w = v^{\text{lcm}(e_1, e_2)}$ and $v_i = v^{\text{lcm}(e_1, e_2)/e_i}$.

Proof.

1. If $v_1^{e_1} = v_2^{e_2}$ and $|v_1|=|v_2|$ then $e_1=e_2$ hence $v_1=v_2$.

2. $v_1^{e_1}=v_2^{e_2}$ for $e_1, e_2\geq 1$. By symmetry wlog $e_1 \leq e_2$ and $|v_1|\geq|v_2|$.
It must be $v_1=v_2x$ for some $x\in\Sigma^*$.
So $v_1^{e_1}=(v_2x)^{e_1}=v_2^{e_2}$, then $(xv_2)^{e_1-1}x=v_2^{e_2-1}$, right multiply by $v_2$ to get $(xv_2)^{e_1}=v_2^{e_2}$.
That is $(v_2x)^{e_1}=(xv_2)^{e_1}\Rightarrow v_2x = xv_2\Rightarrow v_1=v_2x=xv_2$.
From this we have $v_1v_2 = (v_2x)v_2 = v_2(x v_2) = v_2v_1$.
Now, since $v_1 v_2 = v_2 v_1$ we set $n:=|v_1v_2|$ and observe by induction that
if $n=2$ then $v_1=v_2$ and the thesis follows.
Otherwise let $n>2$. There must be a word $y\in\Sigma^*$ s.t. $v_1=v_2y=yv_2$.
Observe $|v_2y|=v_1<|v_1v_2|=n$.
Apply induction hypothesis we see that there must be a word $v\in\Sigma^+$ and integers $a, b>0$ s.t. $v^a=v_2$ and $v^b=y$.
Hence $v_1=v^{a+b}$ and $v_2=v^b$. We pick the longest such $v$.
From $|v|\mid |v_1|, |v_2|$ it must be $|v|=\text{gcd}(|v_1|, |v_2|)$, since otherwise we pick $v^{\text{gcd}(|v_1|, |v_2|)/|v|}$ against the maximality of $|v|$.
Moreover if we set $a':=a+b, b':=b$ observe $e_1a'=e_2b'$ and denote by $l$ such a number.
$l$ is a multiple of both $e_1$ and $e_2$.
Since $v_1^{e_1}=v^l=v_2^{e_2}$ and we picked the longest $v$, there cannot be a smaller such $l$, since otherwise we pick $v^{l/ \text{lcm}(e_1, e_2)}$.
This imply $l=\text{lcm}(e_1, e_2)$, that is $a'=\frac{\text{lcm}(e_1,e_2)}{e_1}$ and $b'=\frac{\text{lcm}(e_1,e_2)}{e_2}$.Q.E.D.

# Non-context-free xcy language.

Excercise from Shallit. Let $L:=\{xcy | x,y\in \{a, b\}^*, y \text{ is a subseq. of } x \}$. Then $L$ is not context free.

Contradics the pumping lemma for context free languages.
Proof. Suppose $L$ is context-free, then there exists $n\geq 1$ such that for every word $w$ with $|w|\geq n$ there exists words $d,x,e,y,f \in \Sigma^*$ such that $|xy| \geq 1, |xey|\leq n$ and $w=dxeyf \in L \iff dx^i e y^i f \in L$ for every $i\geq 0$.

Now pick $w:=a^nb^n c a^n b^n$.

Then $w\in L$. Consider any factorization $dxeyf=w$ s.t. $|xey|\leq n$. We have one of three cases:
1. $xey$ ends exactly in $c$ or at the left of $c$ in $w$.
2. $xey=c$ or $xey$ begins at the left of $c$ in $w$ end ends at the right of $c$ in $w$.
3. $xey$ begins exactly in $c$ or at the right of $c$ in $w$.
Consider the following $i$ values for $d x^i e y^i f$.
Case 1., pick $i:=0$.
Case 2., pick any $i\geq 0$.
Case 3. pick any $i\geq 1$.
Then $d x^i e y^i f\not\in L$ holds for every case. This contradicts the pumping lemma, thus $L$ is not context-free. Q.E.D.

# Paths from cycles

Exercise from Diestel. Let $G$ be a graph and let $C$ be a cycle in $G$. Let $u,v\in C$. Let $P$ be a path from $u$ to $v$ of length (i.e. number of edges) equal to $k$. Then there exists a path in $G$ of length $\geq$ $\sqrt{k}$.

Proof. Wlog $|C|<\sqrt{k}$, otherwise we are done. Let $P\cap C :=\{v_0, \ldots, v_n\}$ and $n < \sqrt{k}$. Let $P_i:=v_i P v_{i+1}$ for every $0\leq i\leq n-1$ and let $m:=max_{i} \{|P_i|\}$. Then $k=\sum_{i=0}^{n} |P_i| \leq \sum_{i=0}^{n} m = mn < m\sqrt{k}$, hence $m>\sqrt{k}$. Let $j$ be such that $|P_j|=m$, then $v_j P v_{j+1} C v_j$ is a cycle of length $l\geq m+1 > \sqrt{k}+1$.Q.E.D..

# Regular languages of finite index

Ex from Shallit. Let $L\subseteq \Sigma^*$ be a language. If $k\geq 1$ is s.t. $L^{k-1}\neq L^{k}=L^{k+1}$ say that $L$ has finite index equal to $k$. Then for every $k\geq 1$ there exists a regular language of finite index equal to $k$.

Proof. Fix $k\geq 1$ and pick $\Sigma$ such that $|\Sigma| = k$.
Let $L_{\leq 1}\subseteq \Sigma^*$ be the language of words containing at most one distinct letter in $\Sigma$. This is a regular language. Then $L^i=L_{\leq i}$ is the language of words containing at most $i$ distinct letters in $\Sigma$. Since $|\Sigma|=k$ one has that $L^{i-1} \neq L^i \neq L^{i+1}$ for every $1 < i < k$ but $L^{k}=L^{k+1}$. Q.E.D.