
%#! platex resume.tex
\documentclass[a4paper]{jarticle}

\usepackage{tani_resume_last}
\usepackage{epic}
\usepackage{eepic}

\alignbeforeskip -5mm
\alignafterskip -5mm
\eqnarraybeforeskip -5mm
\eqnarrayafterskip -5mm

\usepackage{amssymb}
\bibliographystyle{book}
\usepackage{natbib}

\jptitle{�u���C�h�Q�ɂ����鋤�𔻒�v���O�����̎���}
\etitle{A program for conjugacy problem of braids}
\jpauthor{�O�p�@�N��}
\eauthor{Tetsuya Misumi}
\course{�J�@������}
\year{20}
\abstract{%
2000 �N��,�u���C�h (�g�ݕR) �Q�ɂ����鋤����̓���𗘗p�������J���Í��n����Ă��ꂽ�B�{�����ł̓u���C�h�Ō��J���Í��̈��S�������؂����ŕK�v�ƂȂ�v���O��������������B�C�ӂ̃u���C�hV�ɂ����āAV �Ƌ����Ȃ��̂̏W���͖����W���ł��邽�߁A���̗L���W�� summit set �����߂�A���S���Y�������������B}

% �ŏI�X�V�����̑}��
%\compheading
%\setcounter{page}{27}

\begin{document}

\maketitle

\begin{multicols}{2}

\section{�͂��߂�}
 �l�b�g���[�N�����i�񂾍����A���̉B����ړI�Ƃ����Í��Z�p�́A���X�̃Z�L�����e�B�Z�p�̒��j�𐬂����̂�1�Ƃ��Ĉʒu�t�����Ă���B�Í��Ƃ́A�����҈ȊO�ɂ͈Ӗ����킩��Ȃ��悤�ɁA�����g�����߂�ꂽ�菇�ɏ]���ĕϊ���������ȋL���╶���A�܂��͕����̂��Ƃ������B\\
 ~ ���ݍł��L���g���Ă�����J���Í��n�́A�f���������̓���𗘗p���� RSA �Í��n�ł���B���̈Í��n�ł́A2 �̑傫�ȑf���̐ς����Ƃ��Ă���B���S�������߂邽�߂ɂ�蒷�������g�����Ƃ����߂��Ă��邪�A�g�ѓd�b�� IC �J�[�h�̂悤�Ɍ���ꂽ���ő傫�Ȑ����̉��Z���s�����Ƃ͍���ł���ARSA �Í��n�͂��̂悤�Ȋ��ɓK���Ă��Ȃ��B�����ŁA�ȉ~�Ȑ��Í��Ȃǂ̐V�������J���Í��n����������Ă���B\\
 ~ �{�����ł̓u���C�h�Q���g�������J���Í����l����ɓ�����A���S���̍����ƂȂ鋤����̓�������؂����i�̈�Ƃ��āA�v�Z�\�ȗL���W��summit set�����߂�A���S���Y�����������A�Q�O�O�T�N�ɏ��t���ɂ���čs��ꂽ�����Ɣ�r���������B�Q�͂ł̓u���C�h�Q�̊�{�I�Ȓ�`�̉���A�R,�S,�T�͂ł͂��̉��p�ƃu���C�h�Q�ɂ����鍢��Ȗ��̏Љ�A�U�͂ł̓A���S���Y�����Љ�A�V,�W�͂ł͎����ƍ���̉ۑ�Ȃǂ��������B


\section{�u���C�h�Q�̒�`}

\subsection{�u���C�h�Ƃ�}
 n-�u���C�h�Ƃ͕��s�ɕ��ԗ��ݍ����� n �{�̕R�ł���A�E����o�Ă���R�����ǂ�Ə�ɍ��֌������Bn-�u���C�h�Q�̂��Ƃ�$B_n$�ƕ\���B\\

\begin{center}
\includegraphics[width=50mm]{4braid.eps}\\
 4-�u���C�h�̗�
\end{center}

\subsection{�P�ʌ�e}
�P�ʌ�$e$�Ƃ́C�u���C�h�̂����C�R����x���������Ȃ����́B

\subsection{������ t}
�P�ʌ�$e$�ɂ����ďォ�琔����$i$�Ԗڂ�$i+1$�Ԗڂ̕R�݂̂��������Ă���u���C�h�ŁA$i$�Ԗڂ̕R����O�ɂ��Ă�����̂�$t_i$�ƕ\������B����𐶐����ƌĂԁB

\subsection{�t��}
$t_i^{-1}$�́A$t_i$�̕R�̏㉺�֌W���t�ɂ����u���C�h�ł���A$t_i$�̋t���ƂȂ��Ă���B

\begin{center}
\includegraphics[width=50mm]{generators.eps}\\
(a) $t_i$ ~~~~~~~~~~~~~~~ (b) $t_i^{-1}$
\end{center}

\subsection{�u���C�h�̓��l}
2�̃u���C�h$V$,$W$�����l�Ƃ́A����̃u���C�h�̕R�̗��[���Œ肵�A�㉺�֌W���ێ������܂ܓ�������������̃u���C�h�Ɠ������̂ɂł���Ƃ��A2�̃u���C�h�͓��l�ł���Ƃ����B

\subsection{�������ɂ����铯�l�֌W}

\begin{center}
\includegraphics[width=50mm]{samerelation.eps}\\
\end{center}

\begin{enumerate}
\item $t_{i}t_{j} = t_{j}t_{i} \hspace{5em} (|i-j| > 1)$
\item $t_{i}t_{i+1}t_{i} = t_{i+1}t_{i}t_{i+1}$ 
\end{enumerate}


\subsection{��}
2�̃u���C�h$V$,$W$�̐�$VW$�Ƃ́C$V$�̉E�[��$W$�̍��[���q�����u���C�h�̂��Ƃ������B

\subsection{���u���C�h}
$t_i^{-1}$���܂܂Ȃ��u���C�h�B���u���C�h�̏W����$B_n^+$�ƕ\���B

\subsection{��璷�u���C�h}
���u���C�h�̒��łǂ̓�{�̕R�����X��񂾂�����������́B��璷�u���C�h�̏W����$D_n$�ƕ\���B


\subsection{��{�u���C�h}
��璷�u���C�h�̒��łǂ̓�{�̕R����񂾂�����������́B���̃u���C�h��
\[��_n = (t_{1}t_{2} ... t_{n-1})(t_{1}t_{2} ... t_{n-2}) ... (t_{1}t_{2})t_{1}\]�ƕ\����B


\begin{center}
\includegraphics[width=50mm]{omega.eps}\\
 ��{�u���C�h�̗�
\end{center}

\section{canonical form}

\subsection{����}
$X �� D_n$�C$A �� B_n^+$�ɑ΂���, $P = XA$�ƂȂ�Ƃ��C$XA$��$P$�̕����Ƃ����B

\subsection{Left-weighted}
$P$�̕���$XA$��Left-weighted�ł���Ƃ́C�C�ӂ̐��u���C�h$P$�̕���$X'A'$�ɑ΂��āC$X' \leq X$�ƂȂ�Ƃ��������C$X \neg A$�ƕ\���B

\subsection{�W���`�\��}
�W���`�\��
�Ƃ́C$V��B_n$ �ɑ΂��āC$p �� Z$ �Ɛ��u���C�h $A_{1},A_{2},�E�E�EA_{q} �� D_n$ ��p����\[V=��^pA_{1}A_{2}�E�E�EA_{q}\]�Ƃ����\��
��������̂ŁC$1 \leq i \leq q-1$�ƂȂ�e$i$�ɑ΂��A\[A_{i} \neg A_{i+1}\]�����藧�B

\subsection{head,tail}
$a,b,c��B_n^+$�ɂ�����$ab=c$�̂Ƃ��C$a$��$c$��head�Ƃ����C$b$��$c$��tail�Ƃ����B

\subsection{maximal head}
$P$��head $H$��maximal head�ł���Ƃ́C$H$��$H$����菜����$P$��tail��Left-weighted�ƂȂ�Ƃ��������B

\subsection{�W���`�̍���}
�C�ӂ̃u���C�h$V$ ����W���`�����ɂ�, $V$ �� maximal head �� tail �ɕ����C
�X�ɂ��� tail �� maximal head �� tail �ɕ���, ������J��Ԃ�����, �o�Ă��� maximal head �����ɕ\���A�Ō�Ɏc���� tail ��\���B

\section{�u���C�h�Q�ɂ�����v�Z���}

�u���C�h$X$��$Y$�������ł���Ƃ́A$Y = A^{-1}XA$�ƂȂ�u���C�h$A$�����݂���Ƃ��������B
�����Ɋւ��āA����ł���Ɨ\�z
����Ă���v�Z���Ɉȉ��̂悤�Ȃ��̂�����B$B_m$��$m < n$�ɑ΂���$t_1, ... ,t_{m-1}$�ŕ\�����$B_n$�̕����Q�Ƃ���B

\subsection{����������}
\begin{description}
\item[���́F] $(X,Y) \in B_n �~ B_n$
\item[�o�́F] $X$��$Y$�������ł��邩�H
\end{description}

\subsection{����T�����}
\begin{description}
\item[���́F] �݂��ɋ����ł���悤��$(X,Y) \in B_n �~ B_n$
\item[�o�́F] $Y=A^{-1}XA$�ƂȂ�悤��$A \in B_m$
\end{description}

\subsection{��ʋ���T�����}
\begin{description}
\item[���́F] $B \in B_m,m \leq n$�ɑ΂���$Y=B^{-1}XB$�ƂȂ�悤��$(X,Y) \in B_n �~ B_n$
\item[�o�́F] $Y=A^{-1}XA$�ƂȂ�悤��$A \in B_m$
\end{description}

\subsection{���𕪉���}
\begin{description}
\item[���́F] $B \in B_m,m \leq n$�ɑ΂���$Y=B^{-1}XB$�ƂȂ�悤��$(X,Y) \in B_n �~ B_n$
\item[�o�́F] $Y=A'XA''$�ƂȂ�悤��$A',A'' \in B_m$
\end{description}



\section{Summit set}

\subsection{$��$}
�C�ӂ̃u���C�h$V$�Ƀт��{���Ƃ́C$V$�ɑ΂��āC\\
$��^{-1}V��$�Ƃ����ς���邱�ƁB

\subsection{$��^{-1}$}
�C�ӂ̃u���C�h$V$��$��^{-1}$���{���Ƃ́CV�ɑ΂��āC\\
$��V��^{-1}$�Ƃ����ς���邱�ƁB

\subsection{cycling, decycling}
cycling�Ƃ́C�u���C�hV�̕W���`�\����\[V=��^pW_{1}W_{2}�E�E�EW_{q}\]�̂Ƃ��C\[V=��^pW_{2}�E�E�EW_{q}��^{-p}(W_{1})\]�Ƃ�����̂ŁC�����$cyc(V)$�ƕ\���B

\subsection{decycling}
decycling�Ƃ́C�u���C�hV�̕W���`�\����\[V=��^pW_{1}W_{2}�E�E�EW_{q}\]�̂Ƃ��C\[V=��^p��^{p}(W_{q})W_{1}�E�E�EW_{q-1}\]�Ƃ�����̂ŁC�����$decyc(V)$�ƕ\���B

\subsection{inf}
�W���`�\��$W����^{p}W_{1}W_{2}�E�E�EW_{q}$�ɂ�����
\[inf(W)=p\]

\subsection{sup}
�W���`�\��$W����^{p}W_{1}W_{2}�E�E�EW_{q}$�ɂ�����
\[sup(W)=p+q\]

\subsection{summit set}

�C�ӂ̃u���C�hV �ɂ����āAV �Ƌ����Ȃ��̂̏W���̂����A\\
$\lefteqn{C^{sum}(V):=}\\
\hspace{3mm}\left\{S��C(V):
\begin{array}{@{\,}ll@{\,}}
inf(S)=max\{inf(S'):S'��C(V)\}\\
sup(S)=min\{sup(S'):S'��C(V)\}\\
\end{array}\right\}$\\
�𖞂������̂� summit set�Ƃ����B 

\section{�A���S���Y��}

\subsection{summit set �̌���1�����߂�A���S���Y��}
\begin{verbatim}
(INPUT) W �� B_n
(OUTPUT) W �� summit set �̌��̈��
i �� 1
while i��|��|-1 do
  W �� cyc(W).
  i �� i+1.
od
i �� 1
while i��|��|-1 do
  W �� decyc(W).
  i �� i+1.
od
return W.
\end{verbatim}

\subsection{�C�ӂ̂Q�� summit set �̌��������ł��邩�𔻒肷��A���S���Y
 ��}
\begin{verbatim}
(INPUT) V' �� C^sum(V), W' �� C^sum(W)
(OUTPUT ACCEPT �������� REJECT
if inf(V') �� inf(W') or sup(V') �� sup(W')
then return REJECT.
repeat
   guess C �� Dn.
   if C^-1 V' C �� C^sum(V).
   then V' �� �W���`�� C^-1 V' C.
   else return REJECT.
until V'��W'
return ACCEPT.
\end{verbatim}

\newpage

\section{����}
\subsection{�������e}
���t���ɂ��R�̖{����5�{�A�꒷��1�`60�̎��̃u���C�h�������_���ɐ������A����ɑ΂���ő��summit set�̑傫���𒲂ׂ�Ƃ����������s���Ă���B
���͌꒷��1�`10�̎��Ɍ��肵���ׂĂ̑g�ݍ��킹��񋓂��A����ɑ΂���summit set�̑傫���𒲂ׂ��B

\subsection{��������}

\begin{center}
\includegraphics*[width=80mm]{DataOfMatsuba.eps}
���t���f�[�^\\
�@\\
�@\\
�@\\
�@\\
\end{center}

\begin{center}
\includegraphics*[width=80mm]{DataOfMine.eps}\\
�@\\
�O�p�f�[�^
\end{center}

\subsection{�l�@}
���̃f�[�^�͑S�񋓂��Ă���̂ŁA�꒷��1�`10�̂Ƃ��̏��t���̃f�[�^
�̒l�Ɠ��������傫���Ȃ�͂������A�l���������Ȃ��Ă��܂�����������̂ŁA
���t���̃v���O�����Ɣ�r��������K�v������B

\section{����̉ۑ�}
\begin{itemize}
\item �꒷�𑝂₵���ꍇ�őS�񋓂��悤�Ƃ���ƃf�[�^���c��ɂȂ�̂ŁA summit set �̑傫�����傫���Ȃ�悤�ȃf�[�^�̎������l����
\end{itemize}


\begin{thebibliography} {3}
\bibitem{book1}D.B.A.Epstein, James W. Cannon, Word Processing in Group,181-209, 1992
\bibitem{book2}���{��w��w�@������b�Ȋw�����Ȓn����񐔗��Ȋw��U ����15�N�x �C�m�_��, ���t���u, �u���C�h�Q�ɂ����鋤����̌v�Z�ʂɂ���, 2005
\bibitem{book3},Masashi Matsuba and Seiichi Tani:
"On Computational Complexity of the Conjugacy Problem for Braids", �M�w�Z�� COMP-2003-88 (2004-03), pp.17-23. 
\end{thebibliography}

\end{multicols}

\end{document}
