\documentstyle[a4,icai]{article}
\overfullrule 0pt
\pagestyle{headings}
\voffset -10 truemm
\hoffset -12 truemm
\addtolength{\leftmargin}{-5cm}
\def\crrr{}
\begin{document}
\def\underset#1#2#3{{ {\displaystyle #3}\atop {#1} }}
\title{\bf Reconstruction from subwords
\thanks{Supported by the ETIK Grant}}
\authorinheadline{Ligeti, P.}
\titleinheadline{ Reconstruction from subwords }
\author{P\'eter Ligeti \inst{}}
\institute{
Department of Computer Science,
E\"otv\"os Lor\'and University \\
\mbox{e-mail: turul@cs.elte.hu}\\ [4mm]
}
\maketitle
%%\vspace*{-10truemm}
\begin{abstract}
In the presentation two variants of a combinatorial problem for
the set $F_q^n$ of sequences of length $n$ over the alphabet $F_q
= \{0,1,..,q-1\}$ are considered, with some applications. The
original problem was the following: for a given word $w \in
F_q^n$, what is the smallest integer $k$ such that we can
reconstruct $w$ if we know all of its subwords of length $k$. This
problem was solved by Lothaire \cite{loth} .
We consider the following variant of this problem: the $n$-letter
word $w= w_1...w_n$ (which is called a \textsl{DNA-word}) is
composed over an alphabet consisting of $q$ \textsl{complement
pairs}:$\{i,\bar{i} : i = 0,..,q-1\}$; and denote by $w^*$ its
\textsl{reverse complement}, i.e. $w^* = \bar{w}_n...\bar{w}_1$. A
DNA-word $u$ is called a subword of $w$ if it is a subword of
either $w$ or $w^*$. (Another formulation is that we identify $w$
and $w^*$.) We want to reconstruct $w$ from its subwords of length
$k$. We give a simple proof for $k = n-1$, and apply this result
for determining the automorphism group of the poset of DNA-words
of length at most $n$, partially ordered by the above subword
relation.
Some other results on reconstruction and posets of words will be
presented. The results are joint work with P\'eter Erd\H os and
P\'eter Sziklai.
\end{abstract}
\begin{thebibliography}{x}
\itemsep=-3pt
\small
\bibitem[1]{loth} {\sc M. Lothaire}, Combinatorics on words.
{\em Encyclopedia of Mathematics and its Applications}, {\bf 17}. Addison-Wesley Publishing Co., Reading, Mass., 1983.
\end{thebibliography}
\noindent{\Large\bf Postal addresses}
\bigskip
\noindent{\small\em
\parbox{67 truemm}{\noindent {\bf P\'eter Ligeti} \\
Department of Computer Science \\
E\"otv\"os Lor\'and University
1/D, P\'azm\'any P\'eter Street, 1117 Budapest XI.
Hungary }
\end{document}