\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand*\HyPL@Entry[1]{}
\citation{UnoYag00}
\citation{HeberStoye01}
\citation{AhoUll72}
\citation{SattaPeserico05}
\citation{Melamed-naacl03}
\citation{Landau05}
\citation{Zhang-gildea-tr06}
\HyPL@Entry{0<</S/D>>}
\@writefile{toc}{\contentsline {section}{\numberline {1}Introduction}{1}{section.1}}
\citation{AlbertAtkinsonKlazar03}
\citation{sloane}
\@writefile{lof}{\contentsline {figure}{\numberline {1}{\ignorespaces  2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (left) and $((2,1,3,4), (3,4,2,1))$ (right) }}{2}{figure.1}}
\newlabel{fig:twodperm}{{1}{2}{2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (left) and $((2,1,3,4), (3,4,2,1))$ (right)}{figure.1}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2}Multi-dimensional Permutations}{2}{section.2}}
\newlabel{sec:defs}{{2}{2}{Multi-dimensional Permutations}{section.2}{}}
\citation{AlbertAtkinsonKlazar03}
\citation{Zhang-gildea-tr06}
\@writefile{lof}{\contentsline {figure}{\numberline {2}{\ignorespaces  Three-dimensional view of the 2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (top) and $((2,1,3,4), (3,4,2,1))$ (bottom). If we project the cubes onto each axis, we can read off the permutation in each dimension. }}{3}{figure.2}}
\newlabel{fig:3dview}{{2}{3}{Three-dimensional view of the 2-dimensional permutations $((2,1,3,4),(2,3,1,4))$ (top) and $((2,1,3,4), (3,4,2,1))$ (bottom). If we project the cubes onto each axis, we can read off the permutation in each dimension}{figure.2}{}}
\citation{SattaPeserico05}
\citation{ZHGK-naacl06}
\citation{Zhang-gildea-tr06}
\citation{ZHGK-naacl06}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.1}Multi-dimensional Permutation Trees}{4}{subsection.2.1}}
\newlabel{sec:multree}{{2.1}{4}{Multi-dimensional Permutation Trees}{subsection.2.1}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2}Factorization Algorithms}{4}{subsection.2.2}}
\citation{UnoYag00}
\citation{HeberStoye01}
\citation{Landau05}
\citation{BuiXuan05}
\citation{BuiXuan05}
\citation{AlbertAtkinsonKlazar03}
\citation{Zhang-gildea-tr06}
\@writefile{lof}{\contentsline {figure}{\numberline {3}{\ignorespaces  $2$-dimensional permutation trees for $((2,1,3,4),(2,3,1,4))$ (left) and $((2,1,3,4), (3,4,2,1))$ (right). The labels for the intermediate nodes are $2$-dimensional permutations indicating the reordering of the children in each dimension. }}{5}{figure.3}}
\newlabel{fig:twodpermtree}{{3}{5}{$2$-dimensional permutation trees for $((2,1,3,4),(2,3,1,4))$ (left) and $((2,1,3,4), (3,4,2,1))$ (right). The labels for the intermediate nodes are $2$-dimensional permutations indicating the reordering of the children in each dimension}{figure.3}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.3}Uniqueness of Normalized Factorization}{5}{subsection.2.3}}
\citation{ShapiroStephens91}
\citation{DekaiCL}
\citation{ShapiroStephens91}
\@writefile{lof}{\contentsline {figure}{\numberline {4}{\ignorespaces  Spine Rotation }}{6}{figure.4}}
\newlabel{fig:spine-rot}{{4}{6}{Spine Rotation}{figure.4}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3}The number of $k$-ary parsable $d$-permutations}{6}{section.3}}
\newlabel{sec:mathkd}{{3}{6}{The number of $k$-ary parsable $d$-permutations}{section.3}{}}
\newlabel{eq:H}{{1}{7}{The number of $k$-ary parsable $d$-permutations}{equation.3.1}{}}
\newlabel{eq:a}{{2}{7}{The number of $k$-ary parsable $d$-permutations}{equation.3.2}{}}
\newlabel{eq:asimp}{{3}{7}{The number of $k$-ary parsable $d$-permutations}{equation.3.3}{}}
\newlabel{eq:ssimp1}{{4}{8}{The number of $k$-ary parsable $d$-permutations}{equation.3.4}{}}
\newlabel{eq:gen}{{5}{8}{The number of $k$-ary parsable $d$-permutations}{equation.3.5}{}}
\citation{sloane}
\citation{AlbertAtkinsonKlazar03}
\citation{AlbertAtkinsonKlazar03}
\newlabel{eq:simpgen}{{6}{9}{The number of $k$-ary parsable $d$-permutations}{equation.3.6}{}}
\newlabel{eq:ssimp2}{{7}{9}{The number of $k$-ary parsable $d$-permutations}{equation.3.7}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4}Asymptotics of Simple $d$-permutations}{9}{section.4}}
\newlabel{sec:dsimp}{{4}{9}{Asymptotics of Simple $d$-permutations}{section.4}{}}
\citation{AlbertAtkinsonKlazar03}
\citation{Wolfowitz44}
\citation{AlbertAtkinsonKlazar03}
\@writefile{lot}{\contentsline {table}{\numberline {1}{\ignorespaces  The numbers of two-dimensional simple permutations, i.e., $2$-permutations of $k$ that are {\em  not} $k-1$-ary parsable. }}{10}{table.1}}
\newlabel{t:H}{{1}{10}{The numbers of two-dimensional simple permutations, i.e., $2$-permutations of $k$ that are {\em not} $k-1$-ary parsable}{table.1}{}}
\newlabel{eq:simpe}{{8}{10}{Asymptotics of Simple $d$-permutations}{equation.4.8}{}}
\newlabel{l:residual}{{4.1}{10}{}{thm.4.1}{}}
\citation{Wolfowitz44}
\citation{FlSe01}
\citation{FlSe01}
\newlabel{l:pdn2}{{4.2}{11}{}{thm.4.2}{}}
\newlabel{l:dsimp}{{4.3}{11}{}{thm.4.3}{}}
\citation{Zhang-gildea-tr06}
\@writefile{lot}{\contentsline {table}{\numberline {2}{\ignorespaces  The growth rate of $S_{2, k}$, which is the asymptotic ratio of $S_{2, k}[n]/S_{2, k}[n-1]$. }}{12}{table.2}}
\newlabel{t:K}{{2}{12}{The growth rate of $S_{2, k}$, which is the asymptotic ratio of $S_{2, k}[n]/S_{2, k}[n-1]$}{table.2}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5}Growth Rates for Factorizable $d$-permutations}{12}{section.5}}
\newlabel{sec:gog}{{5}{12}{Growth Rates for Factorizable $d$-permutations}{section.5}{}}
\newlabel{l:growth}{{5.1}{12}{}{thm.5.1}{}}
\citation{Odlyzko95}
\newlabel{eq:lowerbound}{{9}{13}{Growth Rates for Factorizable $d$-permutations}{equation.5.9}{}}
\newlabel{eq:geninv}{{10}{13}{Growth Rates for Factorizable $d$-permutations}{equation.5.10}{}}
\@writefile{toc}{\contentsline {section}{\numberline {6}Conclusion}{15}{section.6}}
\@writefile{toc}{\contentsline {section}{\numberline {7}Acknowledgments}{15}{section.7}}
\citation{Zhang-gildea-tr06}
\bibcite{AhoUll72}{{1}{1972}{{Aho and Ullman}}{{}}}
\bibcite{AlbertAtkinsonKlazar03}{{2}{2003}{{Albert et~al.}}{{Albert, Atkinson, and Klazar}}}
\bibcite{BuiXuan05}{{3}{2005}{{Bui-Xuan et~al.}}{{Bui-Xuan, Habib, and Paul}}}
\bibcite{FlSe01}{{4}{2001}{{Flajolet and Sedgewick}}{{}}}
\bibcite{HeberStoye01}{{5}{2001}{{Heber and Stoye}}{{}}}
\bibcite{Landau05}{{6}{2005}{{Landau et~al.}}{{Landau, Parida, and Weimann}}}
\bibcite{Melamed-naacl03}{{7}{2003}{{Melamed}}{{}}}
\bibcite{Odlyzko95}{{8}{1995}{{Odlyzko}}{{}}}
\bibcite{SattaPeserico05}{{9}{2005}{{Satta and Peserico}}{{}}}
\bibcite{ShapiroStephens91}{{10}{1991}{{Shapiro and Stephens}}{{}}}
\bibcite{sloane}{{11}{2006}{{Sloane}}{{}}}
\bibcite{UnoYag00}{{12}{2000}{{Uno and Yagiura}}{{}}}
\bibcite{Wolfowitz44}{{13}{1944}{{Wolfowitz}}{{}}}
\bibcite{DekaiCL}{{14}{1997}{{Wu}}{{}}}
\bibcite{Zhang-gildea-tr06}{{15}{2006}{{Zhang and Gildea}}{{}}}
\bibcite{ZHGK-naacl06}{{16}{2006}{{Zhang et~al.}}{{Zhang, Huang, Gildea, and Knight}}}