\documentclass[11pt]{article}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[dvips]{epsfig}

\usepackage{latexsym}
%\usepackage[polish]{babel}

% for a4 paper:
%\textheight      297mm
%\addtolength{\textheight}{-2in}
%\textwidth       210mm
%\addtolength{\textwidth}{-2in}%

%\oddsidemargin   0mm
%\evensidemargin  0mm
%\topmargin       0em
%\voffset         0em
%\headheight      0em
%\headsep         0em

\newcommand{\myskip}{\vskip 0.4cm \noindent}
\newcommand{\lastcorrections}%
{{
 \begin{sloppypar}
    \baselineskip -0.2in
    \tiny\bf\noindent
last corrections:\\
\end{sloppypar}
}}

\newcommand{\mch}{\mbox{${\cal MC}h$}}
\newcommand{\margincomment}[1]%
    {{%
      \marginpar{{\tiny\begin{minipage}{0.5in}
                       \begin{flushleft}
                          {#1}
                       \end{flushleft}
                       \end{minipage}
                }}
    }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\parskip=.080in

\setlength{\evensidemargin}{0.1in}
\setlength{\oddsidemargin}{0.1in}
\setlength{\textwidth}{6.4in}
\setlength{\topmargin}{0.1in}
\setlength{\textheight}{8.6in}

\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\topsep}{0in}
\setlength{\itemsep}{0in}
\renewcommand{\baselinestretch}{1.2}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% non-math stuff

\newcommand{\myparagraph}[1]{{\smallskip\noindent{\bf #1}}}
\newcommand{\etal}{{\em et al} }
\newcommand{\myif}{{\mbox{\rm\ if \ }}}
\newcommand{\mycase}[1]{\noindent\mbox{{\underline{Case #1}}:\/}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% various leters

\newcommand{\calS}{{\cal S}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% various delimiters

\newcommand{\braced}[1]{{ \left\{ #1 \right\} }}
\newcommand{\angled}[1]{{ \left\langle #1 \right\rangle }}
\newcommand{\brackd}[1]{{ \left[ #1 \right] }}
\newcommand{\parend}[1]{{ \left( #1 \right) }}
\newcommand{\barred}[1]{{ \left| #1 \right| }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% some math symbols

\newcommand{\set}{\,{\leftarrow}\,}
\newcommand{\id}{\mbox{\it id}}
\newcommand{\Prob}[1]{\mbox{\rm Pr}\brackd{\,#1\,}}
\newcommand{\malymax}{{\mbox{\tiny max}}}

\newcommand{\onehalf}{{\mbox{$\frac{1}{2}$}}}

\newcommand{\DoBroadcast}{{\mbox{\sc DoBroadcast}}}
\newcommand{\DoGossip}{{\mbox{\sc DoGossip}}}
\newcommand{\FindMax}{{\mbox{\sc FindMax}}}
\newcommand{\RoundRobin}{{\mbox{\sc RoundRobin}}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% theorem and such

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{fact}{Fact}
\newtheorem{conjecture}{Conjecture}
\newenvironment{proof}{{\it Proof:\/}}{$\Box$\vskip 0.1in}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{\bf  On the Post Correspondence Problem with\\
Partially Commutative Alphabets}

\author{\bf Barbara Klunder \thanks{  Faculty of Math-Inf. Copernicus University, Torun, Poland
                }
        \and
{\bf Wojciech Rytter} \thanks{Instytut Informatyki,
                 Uniwersytet Warszawski, Banacha 2, 02--097,
                Warszawa, Poland, and
                Faculty of Math-Inf. Copernicus University, Torun, Poland
                Email: {\tt rytter@mimuw.edu.pl}.
                }
        }

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%% ABSTRACT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\date{}

\begin{document}

\maketitle

\begin{abstract}
Solvability of a  generalized version of the Post
Correspondence Problem (PCP) to words over  partially commutative alphabets is discussed in the paper.
Solvability is shown for the generalized PCP for two special cases (the case of PCP(2), and the case with one periodic morphism)
Also a weaker version of PCP is discussed which distinguishes (in the sense of solvability) noncommutative from partially commutative
alphabets. This weaker version is solvable for
noncommutative alphabets and unsolvable for partially commutative alphabets.
\end{abstract}
\section{Introduction}

The theory of traces (i.e. monoids with partial commutations)  has
two independent origins: combinatorial problems and the theory of
concurrent systems. Since the fundamental Mazurkiewicz's paper
\cite{M77}, trace languages are regarded as a powerful means for
description of behaviors of concurrent systems. The formal
language theory over traces, limited to recognizable and rational
trace languages, is the subject of \cite{O95}. It is known that
rational expressions with classical meaning are less powerful then
expressions for alphabets which are partially commutative.

Partially commutative alphabets were mostly treated in the theory of traces, in which the symbols represent
some atomic processes and two symbols commute iff they are concurrent (the corresponding
processes can be executed in any order).
A p.c. alphabet (p.c.alphabet, in short) is a finite set $A$
of symbols with a relation $I\subseteq A\times A$ which is   symmetric and irreflexive.
 Such a relation is named the {\it independency relation};
it expresses possibilities of concurrent executions of atomic
actions of systems. The complement $D=A\times A \setminus I$ of
$I$ is named the {\it dependency relation}.

For a given p.c.alphabet $A$ and two words $x,\ y$ we write$x\approx y$ iff one word can be transformed to the other commuting neighboring symbols which are in the relation $I$ of independency. In other words such words are equivalent modulo pairs of symbols whhich commute.

For a pair of symbols $(a,b)$ we denote by $\pi_{a,b}$ the projection which
for a word $w$ removes all letters but $a,b$. For example $\pi_{a,b}(accbacb)\ =\ abab$.
\myskip
\begin{lemma}\label{lemma1}{\rm \cite{HMor}}
\mbox{ \ }\\
$u\approx w$ iff for each
pair $(a,b)\notin I$
$\pi_{a,b}(u)=\pi_{a,b}(w)$.
\end{lemma}


The Post Correspondence Problem (PCP, in short) is probably the first published algorithmically
undecidable combinatorial problem. It is useful tool to establish
undecidability results in different fields of theoretical computer
science. As an example let us recall the problem of emptiness of
intersection of two context-free languages. So we shall study the
decidability results for some special cases.

The original formulation of the problem is as follows: given
elements $(u_i,v_i)\in A^\star\times A^\star$ for $i=1,2,\ldots ,
n$ decide whether there exists a sequence $i_1,\ldots i_m$ of
indices such that $ u_{i_1}\ldots u_{i_m}= v_{i_1}\ldots v_{i_m}$.
Equivalently, for an $n$-element alphabet $X$ we can define two
morphisms $h,g:X^\star \mapsto A^\star$  and decide whether the
equality set:
\[EQ(h,g)=\{ w\in X^+ : h(w)=g(w) \}
\] is nonempty.
\myskip
In case of p.c. alphabet we define the equality set with respect
to the commutation relation:
$$\textrm{EQ}_I(h,g)=\{ w\in X^+ : h(w)\approx g(w) \}$$
The PCP problem for p.c.alphabets is:

given $h,g$ and the relation $I$ check emptiness of $\textrm{EQ}_I(h,g)$.
\myskip
According to Lemma~\ref{lemma1} we can express the equality set for
PCP for p.c.alphabets as a finite intersection of equality sets
for standard (noncommutative) alphabets.

\begin{lemma}\mbox{ \ }\ \
$\textrm{EQ}_I(h,g)\ =\ \bigcap_{(a,b)\notin I}\ EQ(h\cdot \pi_{a,b}, h\cdot \pi_{a,b})$
\end{lemma}
\myskip
\noindent
The only known (positive) result (for PCP with commutative alphabet)
of \cite{IbKim} deals with  the
Parikh equivalence i.e. the case when the p.c. alphabet if
fully commutative.

\section{PCP(2) for partially commutative alphabets}
In this section we assume that $n=2$ and $X=\{0,1\}$. Let us
recall that (generalized) PCP(2) is solvable as was proved by
Ehrenfeucht, Karhum{\"a}ki and  Rozenberg in 1982, see
\cite{EKR1}. On the other hand Matiyasevich and  S�nizergues
shoved that PCP(7) is unsolvable, \cite{MS}. Before we state the
first new result we shall recall the main results of \cite{EKR2}
and \cite{Harju}, which can be find in \cite{HMor} too, concerning
the structure of equality sets in the case of free monoids.  A
morhism $h:X^\star\mapsto A^\star/I$ is periodic if $h(X)\subseteq
u^\star$ for some trace $u$.

Let us assume that  $I=\emptyset$.

\begin{lemma}(\cite{EKR2}) If $h$ and $g$ are periodic then either
$EQ(h,g)=\emptyset$ or $EQ(h,g)= \{ w\in X^\star ;
r(w)=\frac{|w|_0}{|w|_1}=k$ for some $k\geq 0$ or $k=\infty$. If
$h$ is periodic and $g$ is not then $EQ(h,g)$ is empty or equal to
$u^+$ for some nonempty word $u$.
\end{lemma}

So equality sets are regular or context-free. The number
$r(w)=\frac{|w|_0}{|w|_1}$ is called the \textit{ratio} of a word
and it is decidable if the intersection of regular sets  and (or)
sets of words of a given ratio is nonempty. In the case of two
non-periodic morphisms the equality set is always regular. For two
periodic morphisms, $EQ(h,g)$ can be  nonempty only when
$h(X),g(X)\subseteq u^\star$ and then $r$ can be easily find.

\begin{lemma} Let $(h,g)$ be a pair of  non-periodic morphisms
over a binary alphabet. If the equality set $EQ(h,g)$ is nonempty
then it is  either of the form
\begin{enumerate}
  \item $(u+v)^+$ for some words $u,v$, or of the form
  \item  $(uv^\star w)+$ for some words $u,v,w$.

\end{enumerate}

\end{lemma}
The constructive  result of \cite{Harju} is the following:
\begin{lemma} Let $K$ be a family of morhisms for which
generalized PCP is decidable and let $h,g \in K$. If $EQ(h,g)$ is
regular then $EQ(h,g)$ can be effectively  found.
\end{lemma}
Combining all those results with Theorem \ref{t1} we obtain the
following:

\begin{theorem}\mbox{ \ }\ \  PCP(2) is solvable for
partially commutative alphabets.
\end{theorem}


\section{PCP with one periodic morphism}
In the classical version of PCP there are known classes of
morphisms for which the problem is effectively solvable. We shall
 consider one of them: periodic morphisms. It is enough to assume that one
 of the morphisms is
periodic. We shall need lemma, which states a property of the one
counter languages, see \cite{Ib},\cite{Halva}.


\begin{lemma} \label{l1} Let $\rho: X^\star \mapsto  Z $ be a monoid morphism into the additive
group of integers and let $R \subseteq AX^\star $ be a  language
recognized by a reversal-bounded multicounter machine. It is
decidable whether $\rho^{-1}(0)\cap R\neq\emptyset$ .
\end{lemma}

\begin{proof} Here the language $\rho^{-1}(0)$ is a one counter and
reversal-bounded
 language and
 reversal-bounded languages are closed under intersections. The
emptiness problem is decidable for those languages, see \cite{Ib}.
\end{proof}

The proof of the next theorem adopts similar arguments as the
classical one, \cite{HMor}.


\begin{theorem}
 PCP is decidable for instances $( h, g )$, where h
is periodic and the alphabet is partially commutative.
\end{theorem}


\begin{proof}
 Let $h,g : X^\star \mapsto A^\star/I$ and assume that h is periodic and $h
 (X) \subseteq u^\star$ for a trace $u$. Let $(a,b)\in D$, then the equality set of
 $(\pi_{a,b}h,\pi_{a,b}g)$ is the intersection of a regular and a
 multicounter reversal bounded language.
But from Lemma \ref{l1} the equality set of $(h,g)$ is the
intersection of such languages too.


Define  a morphisms $\rho$ by $\rho( a ) = | h ( a ) |- | g ( a
)|$, for all $a \in X$ . Define a  set $R = g^{-1}(
u^\star\setminus \{\varepsilon\}$. Now
\[\rho^{-1}(0)=\{ v :|h)(v)|=|g(v)| \}
 \] and $w \in \rho^{-1}(0)\cap R$  if
and only if $w \neq \varepsilon , g ( w ) \in  u^\star$ and $| g (
w ) | = | h ( w ) |$. In other words we have $g ( w ) = h ( w )$
for some $w \neq \varepsilon$ if and only if $\rho^{-1}(0)\cap
R\neq\emptyset$ . By Lemma \ref{l1} the latter property is
decidable and therefore the claim follows.
\end{proof}

\section{Weak PCP for partially commutative alphabets}

Define the {\em Weak } PCP with parameters $r,s$  the problem:

given the words $x_1\cup x_2\cup \ldots x_r,\ y_1\cup y_2\cup \ldots y_s)$ over p.c. alphabet;

test if $\textrm{Weak-EQ}(h,g)=\emptyset$, where
$$\textrm{Weak-EQ}(h,g)\ = \{(i_1,i_2,\ldots, i_p,\ j_1,j_2,\ldots j_q)\ :\ x_{i_1} x_{i_2} \ldots x_{i_p}\
\approx \ y_{j_1}y_{j_2}  y_{j_q}\ \}$$
$\textrm{Weak-EQ}(h,g)$ is called here the weak equality set.
\myskip
\noindent Denote by $\textrm{Weak-PCP}(s,r)$ the weak PCP in which the domain of$h$  is of size $s$ and
the domain of $g$ is of size $r$.
%
\myskip
The natural relation of PCP for noncommutative alphabets  to $\textrm{Weak-PCP}$ for p.c. alphabets is as follows.
Assume we have an instance of PCP given by
$(u_i,v_i)$ for $i=1\ldots k$, where $u_iv_i\in A^+$.
Assume $A\cap \{1,\ldots,k\}l\ =\ \emptyset$
Let the p.c. alphabet be  $A\cup \{1,\ldots,k\}$, where
all letters in $A$ commute with all letters in $\{1,\ldots,k\}$, and no other pairs of
different letters commute. Define $$\forall\ 1 \le i \le k\ \  h(i)=i\;u_i,\ g(i)=i\;v_i$$ 
\myskip
Then we can express in a natural way the PCP(k) problem as a $\textrm{Weak-PCP}C(k,k)$ with
morphisms $h,g$ defined above. It is known that $PCP(7)$ is unsolvable, hence $\textrm{Weak-PCP}(7,7r)$
is also unsolvable.
\myskip
We know that $PCP(2)$ is decidable (also for p.c. alphabets), this would
suggest that $\textrm{Weak-PCP}(2,k)$ is solvable. However this suggestion is wrong.
\myskip 
\begin{theorem}\mbox{ \ }\\
{\bf (a)}\
\textrm{Weak-PCP}(s,r) is solvable for any $s,r$ and  noncommutative alphabets
\\
{\bf (b)}\ $\textrm{Weak-PCP}(2,7)$ is  unsolvable for
partially commutative alphabets.
\end{theorem}
\begin{proof}
Let $\overline{\Sigma}$ be the disjoint copy of $\Sigma$, by $\overline{v}$ we mean the
word $v$ with  each letter  $v[i]$ changed to its copy  $\overline{v[i]}$.

Then the unsolvable PCP(7) problem  for lists $(u_1,u_2,\ldots u_7)$ and $(v_1,v_2,\ldots v_7)$, where $u_i,v_i$ 
are  words over the alphabet $\{a,b\}$,
is reduced to the problem $\textrm{Weak-PCP}(2,7)$ as follows:
%
$$h(1)=a\;\overline{a},\ h(2)= b\;\overline{b})$$
$$\forall\ 1 \le i \le 7\ \  g(i)=u_i\;\overline{v_i}\ \forall\ 1 \le i \le 7$$
%
%The language on the left side is the fixed twin shuffle language.
Assume that the commutation relation is $\Sigma \times \overline{\Sigma}$.
Then $PCP(k)$ has a solution iff $\textrm{Weak-PCP}(2,7)$ has a solution for the morphisms $h,g$ constructed above. 
This completes the proof.
\end{proof}
\myskip
{\bf Open problem}:

 Is $\textrm{Weak-PCP}(2,2)$ solvable ?

\begin{thebibliography}{1}


\bibitem{CL87}M. Clerbout, M.
Latteux: {\it  Semi-commutations.} Information \& Computation 73,
pp. 59-74, 1987.

\bibitem{DR95}V. Diekert, G. Rozenberg (eds.): {\it  The
Book of Traces}. World Scientific, 1995.
\bibitem{EKR1}A. Ehrenfeucht, J. Karhum{\"a}ki,G. Rozenberg:
{\it The (Generalized) Post Correspondence Problem with Lists
               Consisting of two Words is Decidable}. Theor. Comput. Sci.
               21,pp. 119-144, 1982.
\bibitem{EKR2} A. Ehrenfeucht, J. Karhum{\"a}ki,G. Rozenberg:
{\it On Binary Equality Sets and a Soliution to the Set Conjecture
in the Binary Case}. Jornal of
               Algebra, 85,pp. 76-85, 19823.
\bibitem{GR} A. Gibbons, W. Rytter: {\it On the Decidability of Some Problems About Rational Subsets
of the Free Partially Commutative Monoids}, TCS 48, pp. 329-337,
1986.
\bibitem{Halva}Vesa Halava, Tero Harju, Mika Hirvensalo: Binary (generalized) Post Correspondence Problem.
 Theor. Comput. Sci. 276(1-2): 183-204 (2002)
 \bibitem{HMor} T. Hajru, J. Karhum{\"a}ki: {Morphisms}, in
 Hanbook of formal languages Vol. 1.  G rozenberg A Salomaa, eds. Springer 1997
\bibitem{Harju}Tero Harju, Juhani Karhum�ki, Daniel Krob: Remarks on Generalized
Post Correspondence Problem. LNCS 1046 STACS 1996: 39-48
\bibitem{HMU01}J.E. Hopcroft, R. Motwani, J.D. Ullman: {\it  Introduction to
Automata Theory, Languages and Computation}. Addison-Wesley, 2001.
\bibitem{Ib} O.H. Ibarra: {\it Revelsal-Bounded Multicounter Machines and Their Decision
Problems}. Journal of the ACM 25 (1), pp. 116-133, 1978.
\bibitem{IbKim} O.H. Ibarra, C.E. Kim: {\it A useful device for showing the solvability
of some decision problems}. Proc. of the Eight Annual ACM
Symposium on Theory of Computing (1976), pp. 135-140.

\bibitem{MS}Yu. Matiyasevich, G. S�nizergues: Decision Problems for Semi-Thue Systems with a Few Rules. LICS 1996: 523-531
\bibitem{M77} A. Mazurkiewicz: {\it  Concurrent Program Schemes
and Their Interpretations}. Report DAIMI-PB-78, Aarhus University,
1977.




\bibitem{O95} E. Ochma\'{n}ski: {\it  Recognizable Trace Languages}. In \cite{DR95},
pp.167-204. World Scientific, 1995.




\end{thebibliography}

\end{document}
