\documentclass[10pt]{jsarticle}
\usepackage[dvipdfm]{graphicx}
\usepackage{url}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{float}
\usepackage[top=30truemm,bottom=25truemm,left=20truemm,right=20truemm]{geometry}
\usepackage{latexsym}
\usepackage{listings}
\pagestyle{empty}
\newcommand{\beforesection}[1]{
 \vspace{-#1mm}
}


\makeatletter
\newcommand{\xRightarrow}[2][]{%
\ext@arrow 0055{\Rightarrowfill@}{#1}{#2}%
}
\def\Rightarrowfill@{\arrowfill@\Relbar\Relbar\Rightarrow}
\newcommand{\xLeftarrow}[2][]{%
\ext@arrow 0055{\Leftarrowfill@}{#1}{#2}%
}
\def\Leftarrowfill@{\arrowfill@\Leftarrow\Relbar\Relbar}
\newcommand{\xLongleftrightarrow}[2][]{%
\ext@arrow 0055{\llrafill@}{#1}{#2}%
}
\def\llrafill@{\arrowfill@\Leftarrow\Relbar\Rightarrow}
\makeatother


\title{第2章}
\begin{document}
\maketitle

第二章では論文で使う概念や用語の定義やその説明などを行う．

\section{可逆プログラミング言語janus}
可逆プログラミング言語janusとは，C言語に似た構文に加えて可逆性を保証する
ための構文要素をもつ．今回用いるjanusは単射関数しか表すことができないという意味で
可逆であることが証明されている．\\
例を用いて可逆プログラミング言語janusについて説明する．以下のプログラム
は二項係数を計算するプログラムをjanusで記述したものである．
\begin{lstlisting}[basicstyle=\ttfamily\footnotesize]
1:   procedure binom(int n, int k, int r) // binomial coefficient
2:      if k >= 0 then
3:         r += 1
4:            local int i = 0
5:               from i = 0 loop i += 1
6:                  local int tmp = r*(n+1-i)/i
7:                     r <=> tmp
8:                  delocal int tmp = r*i/(n+1-i)
9:               until i = k
10:           delocal int i = k
11:     fi k >= 0
12:
13:  procedure main()
14:    int n = 6
15:    int k = 3
16:    int result
17:    
18:    call binom(n,k,result)
 \end{lstlisting}
janusの構文と意味論の概要を例を用いて示す．変数の基本型は，整数型，整数
型の配列とスタックである．janusでは非単射なものを扱うことができないため，
単純な代入$x:=1$のように記述することができないが，かわりに3,5行目のよう
に複合代入演算子 +=,-=,\verb|^|= を用いて記述することができる．ただし，
複合代入演算子式$x+=e$の左オペランド$x$であらわれるオブジェクトが右オペ
ランドの式$e$にあらわれてはならず，左オペランドが添字演算子式の場合
$(x[a]+=e)$はその添字$a$にもあらわれてはならない．この制約は$x+=x$のよう
な非単射な計算を行う記述をできないようにするために必要である．
\section{ランク計算}


 \subsection{二分木}
二分木とは，一つの節に対して多くても2つ以下の子を持つような木を二分木とよぶ．


 \subsection{自然順序}


 \subsection{二分木の表現}

 
 \subsection{二分木のランク}


\section{可逆シミュレーション}
 

 \subsection{単射化}
単射化を説明するうえでまずは単射や写像について説明する．写像とは二つの集
合AとBがあり，Aの各要素aに対してBの要素bが１つ対応しているとき，この対応
をAからBへの写像といい，対応する要素を$b=f(a)$のように表す．また，$f$が集合A
からBへの写像であることを$f:A→B$と表す．集合Bが実数や複素数の集合のときは，
写像のことを関数と呼ぶ．単射とは，集合から他の集合の中への１対１の写像の
ことである．すなわち，集合Aから集合Bへの写像$f$が単射であるとは，$a，b \in
A$
，$a \neq b$なら，$f(a) \neq f(b)$であること，あるいは対偶をとって，
$f(a)=f(b)$なら$a=b$であることを意味する．単射であるということは，１対１
の写像なので可逆であるといえる．単射なものと単射ではないものの
例を挙げると，まず集合Aと集合Bの要素をそれぞれ$a1,a2 \in A$，
$b1,b2 \in B$として，写像$f1,f2$を次の規則で用意したとき，$f1(a1)=b1
\cap  f1(a2)=b2$，
$f2(a1)=b1  \cap  f2(a2)=b1$写像$f1$は単射で写像$f2$は単射ではない．
単射化とは単射もしくは単射ではない関数を拡張して単射な関数にすることである．
記号を用いて単射化を定義する．任意の関数$ｆ：A→B$に対して，ある$C$が存在
して任意の$ｘ \in A$に対して$fst(f'(x))=f(x)$となる単射関数$f':A→B×C$が存在する．$fst$は$fst(x,y)=x$となる関数である．必ずしも単射にならない関数$f$から上記の条件を満たす単射関数$f'$を
作ることを単射化という．このときの$C$の要素は，元の関数$f$の出力にはで
ないことからゴミ出力という．また，$C$がスタックの場合は$C$に属するスタックをゴミスタックと呼ぶ．


 \subsection{可逆化}
 可逆とは，ある状態から違う状態に遷移したとき遷移した状態から元の状態に
 戻ることができることである．可逆化とは，非可逆なものを可逆なものに変え
 ることである．可逆化を行う方法としてbennettによる一般解法がある．この一
 般解法とは，非可逆なアルゴリズムについてもゴミ情報となる入力を特定する
 ための情報を出力に追加することで可逆にすることができるという方法である．

 \subsection{埋め込み}
埋め込みとは，非可逆なプログラムで代入などによって失われるデータや制御情
報をすべて記憶するようにプログラムを変換することで可逆なプログラムに作り
替える方法である．埋め込みによる可逆シミュレーションの実行には，時間計算
量，空間計算量，消去情報量，および実時間性などの観点でトレードオフをもつ
手法が提案されている．    


 \subsection{シミュレーション}


 


\end{document}