\documentclass[dvipdfmx,14pt, aspectratio=169]{beamer}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb}
\usepackage{mathtools}
\usepackage{pifont}% http://ctan.org/pkg/pifont


\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\1}{\mathbf{1}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\A}{\Sigma}
\newcommand{\MA}{{{\A}^{\ast}}}
\newcommand{\Aset}{\A\text{-}\Set}
\newcommand{\Atmt}{\mathbf{Atmt}}
\newcommand{\ofAset}{\A\text{-}\Set_{\text{o.f.}}}
\newcommand{\ofAtmt}{\mathbf{Atmt}_{\text{o.f.}}}
\newcommand{\memo}[1]{{\color{red}メモ: #1}}
\newcommand{\demph}[1]{\textbf{#1}}
% \newcommand{\Lan}{\mathcal{L}\textrm{angage}}
\newcommand{\Lan}{\textrm{Langage}}

\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}

\usetheme{Darmstadt} 
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{theorems}[default]
\setbeamertemplate{blocks}[default]
\AtBeginSection[]
{
  \begin{frame}
    \frametitle{Table of Contents}
    \tableofcontents[currentsection]
  \end{frame}
}

\title{オートマトン理論の道具としてのtopos}
\author{洞龍弥}
\institute[]{東京大学数理科学研究科博士1年}
\date[2024年8月30日]{2024年8月30日\\}

\begin{document}

\begin{frame}
\titlepage
\end{frame}


\section{自己紹介}

\begin{frame}{自己紹介}
\begin{description}
    \item[氏名] 洞龍弥
    \item[所属1] 東京大学数理科学研究科博士1年
    \item[所属2] 国立情報学研究所(NII)RA
    \item[興味] 最近は圏論，topos理論，coalgebra, など
    \pause
    \item[近況] Topos$\times$automataにかなりワクワクしている！
\end{description}
\end{frame}



\begin{frame}{個人的経験}
% オートマトンは専門ではないが，個人的には特別な存在．
\begin{enumerate}
    \item[B1] 進化論の授業でオートマトンを知る．(注)
    \item[B1]圏論的な最小化問題について自由研究をする．[pdf 1]
    % (implicitにtoposに触れる) 
    \item[B4] Sipserでオートマトンを学ぶ．[pdf 2]
    % Powerset constructionの豊穣圏的な
    \item[M?] オートマトンがToposを為すことに気づく．
    \item[M2] Sin'ya先生の話を聞き，profinite group toposとの関係に気づく
    \item[D1] 局所有限オートマトンがtoposを為すことに気づく．(本気になる！)
    \item[D1] word-action toposでtoposの未解決問題が解ける!(j.w.w. Yuhi Kamio)
\end{enumerate}
\end{frame}

\begin{frame}{この発表で伝えたいこと:}

\begin{enumerate}
    \item[\xmark] Topos理論との詳細な関係を解説(pdf執筆中)
    \item[\xmark] オートマトン理論がtopos theoristにとってなぜ興味深いか
    \item[\xmark] オートマトン理論の層理論($\simeq$topos理論)的な幾何学的再解釈
    \item[\xmark] なぜ今，このテーマが現実的なのか？ (Morgan)
    \item[\cmark] \textbf{オートマトン理論においてtopos理論が有用かもしれないこと}
\end{enumerate}
\end{frame}

\begin{frame}{免責事項}
    私の興奮は，抽象的なアイデアと具体的な計算が噛み合ったことによるものなのであって，したがって決して一方を説明することで共有できるものではない．しかし，私は今日前者についてしか話さない．

    \pause

    それでも面白いと信じてる！
\end{frame}





\input{WholePicture}

\begin{frame}{橋の建設}
    Topos理論(や圏論)は，多くの数学の分野に橋をかけてきた．

    \pause

    正直，橋がかかりそうな場所はまだ大量にある．大事なのは，次を問うこと．
    \begin{itemize}
        \item 橋を通じて何を運びたいか？
        \item それを運べるだけの強靭な橋を作れるか？
    \end{itemize}
    Toposによる架橋という意味では，オートマトン理論と幾何学に一番可能性を感じている．
\end{frame}

\begin{frame}{}
Toposがオートマトン理論に何をもたらせるか

\begin{itemize}
    \item 統一言語として
    \begin{itemize}
        \item coalgebraic approach
        \item algebraic approach (classes of (finite) monoids)
        \item Topological (profinite) approach
        \item ...
    \end{itemize}
    \item 幾何学との橋として
    \begin{itemize}
        \item Sheaf theoretic intuition
        \item 幾何学的不変量 (fundamental group, cohomology, ...) 
        \item Galois theory
    \end{itemize}
\end{itemize}
\end{frame}

\section{Related works}
\begin{frame}{圏論$\times$オートマトン}
    \begin{itemize}
        \item Coalgebraic (or manadic) approach {\small(古典的，超綺麗で面白い！)}
        {\tiny
        \begin{itemize}
            \item {}[Adámek,
Free algebras and automata realizations in the language of categories. 1974]
\item {}[Goy, \textbf{Petrişan}, and Aiguier, Powerset-Like Monads Weakly Distribute over Themselves in Toposes and Compact Hausdorff Spaces, 2021]
            % \item 教科書 [Jacobs, Introduction to Coalgebra.  2016] がある．
        \end{itemize}
        }
        \item Functorial approach {\small(最小化問題や一般化へ)}
        {\tiny
        \begin{itemize}
            \item{} [Colcombet and Petri, Automata Minimization: A Functorial Approach. 2020]
            \item{} [Iwaniack, Automata in toposes, and general Myhill-Nerode theorems. 2023]
        \end{itemize}
        }
        \item Topos \textbf{of} automata
        {\tiny
        \begin{itemize}
            \item {}[Lawvere, Functorial concepts of complexity for finite automata. 2004]
            \item \textbf{我々！} "topos-geometry of automata"
        \end{itemize}
        }
    \end{itemize}
\end{frame}


\section[導入]{導入: Grothendieckの肩に乗る}

\begin{frame}{我々のやること}
各種のAutomatonがtoposを成す！(びっくり)
\begin{description}
    \item[これまで] toposの中でオートマトン理論をやる
\begin{center}
    $\leftarrow$ topos $=$ 数学の宇宙
\end{center}
\item[我々] topos of automataを使って幾何学を展開する
\begin{center}
    $\leftarrow$ topos $=$ 空間
\end{center}
\end{description}
\end{frame}

\begin{frame}{Toposとは: 権威主義タイム(1/3)}
\begin{columns}
    
    \begin{column}{0.3\textwidth}
        \begin{figure}
            \centering
            \includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
            \caption{Grothendieck}
        \end{figure}
    \end{column}
    \begin{column}{0.7\textwidth}
        \textit{トポスのテーマは，スキームのテーマから生まれました．スキームが出現したのと同じ年です---しかしトポスのテーマは，その広がりにおいては，遥かに源になったスキームのテーマを超えています．}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}{Toposとは: 権威主義タイム(2/3)}
\begin{columns}
    
    \begin{column}{0.3\textwidth}
        \begin{figure}
            \centering
            \includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
            \caption{Grothendieck}
        \end{figure}
    \end{column}
    \begin{column}{0.7\textwidth}
        \textit{幾何学と代数，トポロジーと数論，数理論理とカテゴリー論，連続の世界と「不連続」または「離散」構造の世界が結び合う，この「ベッド」，あるいはこの「深い川」は，スキームのテーマではなくて，トポスのテーマです．}
    \end{column}
\end{columns}
\end{frame}

\begin{frame}{Toposとは: 権威主義タイム(3/3)}
\begin{columns}
    
    \begin{column}{0.3\textwidth}
        \begin{figure}
            \centering
            \includegraphics[width=1\linewidth]{Alexander_Grothendieck.jpg}
            \caption{Grothendieck}
        \end{figure}
    \end{column}
    \begin{column}{0.7\textwidth}
        スキームのテーマが新しい幾何学の核心としてあるとすれば，トポスのテーマはこの幾何学の外皮あるいは住まいです．それは，豊かな幾何学的響きを持つ同一の言語によって，\textbf{数学上の事柄からなる広大な宇宙のあれこれの地域から由来する，相互に非常に隔たった状況に共通する「エッセンス」を繊細に捉える}ために私がひろく構想したものです．
    \end{column}
\end{columns}
\end{frame}

\begin{frame}{先例: Toposの生まれと数論幾何学}
    Grothendieckは，Weil予想(リーマン予想の有限体類似)を解くために，幾何学を操作論的に刷新した．
    \[
    \text{空間} \leftarrow\text{操作}
    \]
    これにより，数論を含むまでに空間概念を拡張し，数論に"幾何学的操作"を輸入した．
\end{frame}

\begin{frame}{野望}
Grothendieckが数論に対してやったことを，(Grothendieckの作った道具をそのまま用いて)オートマトン理論でやる！
\end{frame}

\begin{frame}{Topos(不本意な定義)}
    \begin{definition}[Topos]
         圏$\E$が\demph{(Grothendieck) topos}であるとは，
         \begin{itemize}
             \item ある小圏$\C$と忠実充満な埋め込み
         $i\colon \E\hookrightarrow \PSh(\C)$が存在し，
         \item さらに$i$の左随伴$L$が存在し
         \item さらに$L$が全てのfinite limitを保つことをいう．
         \end{itemize}
    \end{definition}
    要は,
\pause

    \begin{center}
        Grothendieck topos $=$ 特別いい感じの圏．
    \end{center}
\end{frame}

\begin{frame}{Topos}
    \begin{example}[Sheaf topos]
        位相空間(やlocaleやsite)$X$について，$X$上の層の圏$\mathbf{Sh}(X)$はtoposである．
    \end{example}
    $\downarrow$これだけでいい
    \begin{example}[Presheaf topos]
        小圏$\C$について，$\C$上のpresheafの圏$\PSh(\C)\coloneqq [\C^\op,\Set]$はtoposである．
    \end{example}
\end{frame}

\begin{frame}{Toposはレア！}
\begin{enumerate}
    \item Toposは(その目的からして)かなり手を動かせる幾何学を展開してくれる．
    \item しかし，興味ある数学的対象がtoposをなすことはレアで，いかにトポスを構成するかが肝心．
    \begin{itemize}
        \item $\mathbf{Top},\mathbf{Scheme},\mathbf{Ab},\mathbf{CRing},\mathbf{Group},\mathbf{Vect}$はtoposではない．
    \end{itemize}
    \item (いろんな)Automataはそれ自体が(いろんな)toposを成す！
\end{enumerate}
    
\end{frame}

\begin{frame}{ここまでのまとめ}
    \begin{itemize}
        \item[idea] Toposは空間概念の拡張のためにGrothendieckが考案した，位相空間の一般化(注)である．
        \item[idea] 興味ある数学的対象自体がtoposを為すのはレア．
        \item[idea] Toposがあれば，(かなり手を動かせる幾何学が展開できる．)
        \item[fact] Toposは，物としては非常に特別な性質($\neq$? 構造)を持った圏である．
        \item[fact] Presheaf categoryはtoposである．
    \end{itemize}
    \memo{アイデアは幼稚，計算によって実感が湧く．本当は計算についても話したい．}
\end{frame}


\section[第一のtopos]{第一のtopos: \texorpdfstring{$\Aset$}{Sigma-set}}

\begin{frame}{定義$\Aset$}
\begin{itemize}
    \item $\A$は(有限とは限らない) set of alphabets.
    \item $\MA\coloneqq \coprod_{n\geq 0}\A^n$は$\A$の有限文字列の集合．
    \item $\A$-setとは，$(Q,\delta\colon Q\times \A\to Q)$.言い換えれば，集合$Q$への右$\MA$作用
    % \item Automatonとは，$(Q, \delta\colon Q\times \A \to Q, F\subset Q)$のこと．(始点はデータに入れない．)
\end{itemize}
\begin{definition}
    $\Aset$ は$\A$-setとその作用を保つ写像の圏．
\end{definition}
\begin{proposition}[$\A$-sets form a topos]
    $\Aset \simeq \PSh(\MA)$はpresheaf categoryで，特にtopos.
\end{proposition}
\end{frame}

\begin{frame}{空間($\neq$位相空間)としての$\Aset$}
絵に描くのはすごく難しい．
\begin{itemize}
    \item ブーケ$\bigvee_{a\in \A}S^1$の性質と，
    \item カントール空間$\A^{\omega}$の性質
\end{itemize}
を併せ持っている．
\begin{figure}
    \centering
    \includegraphics[width=1\linewidth]{pictures/WhyBouquetAndCantor.jpeg}
\end{figure}
\end{frame}

\begin{frame}{ブーケっぽい空間としての$\Aset$}
\begin{proposition}[Easy]
    $\Aset$は連結かつ局所連結
\end{proposition}
\begin{proposition}[Easy]
    $\Aset$の基本群は$\A$で生成される自由群．
\end{proposition}
\end{frame}

\begin{frame}{カントール空間っぽい空間としての$\Aset$}
    \begin{proposition}[Points {[Hora 準備中]}]
        $\Aset$はsurjective pointを一つ持ち，他に$\omega$-wordsの同値類\footnote{最初の有限文字をeditする操作の同値類}ごとに一つpointがある．\memo{本当は話したい！}
    \end{proposition}
    \begin{proposition}[Subspaces {[Hora, Iwaniack, and Morgan 準備中]}]
        $\Aset$のsubspaceは，$\A^{\omega}$の`自己相似部分空間\footnote{localeとして}'と一対一に対応する．\memo{本当は話したい！}
    \end{proposition}
\end{frame}

\begin{frame}{Digression}
    \begin{proposition}[`Quotients' {[Kamio, Hora 2024]}]
        $|\A|\geq\omega$なら，$\Aset$のquoteintはproper class個ある．特に，Lawvereの未解決問題第一番は肯定的に解決される！
    \end{proposition}

    \begin{question}
        トンプソン群($T$?)との関係性．よっぽど$\A^{\omega}/T$っぽい．
    \end{question}
    
\end{frame}

\begin{frame}{Quotient$\to$ Language class対応}
    \begin{proposition}
    $\Aset$のQuotient toposがあると，言語クラスが一つ定まる．
    \end{proposition}

    \begin{example}
        $\mathbf{Cont}(\widehat{\MA})$に対応する言語クラスは正則言語．
    \end{example}
    \begin{example}
        $\mathbf{Cont}(\widehat{F\MA})$に対応する言語クラスは群言語．
    \end{example}
\end{frame}



\begin{frame}{ここまでのまとめ}
    
\end{frame}

\section[{第二のtopos}]{第二のtopos: \texorpdfstring{$\Atmt$}{Atmt}}
\begin{frame}{定義 $\Atmt$}
この発表のオートマトンの定義には，始点や有限性は含めない\footnote{後に出てくる．}

\begin{definition}[$\Atmt$]
    オートマトンとは，集合$Q$と写像$\delta\colon Q\times \A\to Q$と部分集合$F\subset Q$の組 $(Q, \delta, F)$．オートマトンと，オートマトンの構造を保つ写像の圏を$\Atmt$と書く．
    % 射とは，これらの構造を保つ写像．オートマトンの圏
\end{definition}
\end{frame}

\begin{frame}{$\Atmt$ はトポス}
    \begin{definition}[言語の圏]
        言語が対象で，射$L\to L'$が$w\in \MA$で$L=w^{-1}L'$なるものとすると，圏$\Lan$ができる．これを\demph{言語の圏}という．
    \end{definition}

    \begin{theorem}[オートマトン=言語上の前層]
        $\Atmt\simeq \PSh(\Lan)$. 特に，$\Atmt$はtopos.
    \end{theorem}
    スペインでのVictorの反応: 
    \pause
    `No Way!'
\end{frame}

\begin{frame}{$\Atmt$と言語認識}
$\Atmt$は実は"coalgebraの圏"というものになっている．次はcoalgebra界隈では有名な話．
\begin{definition}
    \demph{The automaton of languegaes} $\1\coloneqq (\P(\MA), \delta, F)$は，状態集合が言語全体で，$\delta(L,a)=a^{-1}L$, $L\in F\iff \varepsilon\in L$なるautomaton.
\end{definition}
    \begin{theorem}[古典的な定理]
        $\Atmt$のterminal objectは$\1$であり，terminal への一意的な射$!\colon (Q, \delta, F)\to \1$は$q\in Q$を($q$を始点とした時に)認識される言語に移す．
    \end{theorem}
\end{frame}

\begin{frame}{$\Atmt$ の幾何学(かなり未知)}
\begin{proposition}[Essential points ($\subset$ points)]
    $\Atmt$のessential point と言語$L\in \P(\MA)$は一対一に対応する.
\end{proposition}

\begin{proposition}[Open subtopoi ($\subset$ Subtopoi)]
    $\Atmt$のopen subtoposと言語クラス$C\subset \P(\MA)$で
    \[
    L\in C \implies w^{-1}L\in C (\forall w\in \MA)
    \]
    なるものは一対一に対応する．
\end{proposition}
\end{frame}

\begin{frame}{$\Atmt$ の幾何学(かなり未知)}
\begin{proposition}[局所連結性]
    $\Atmt$は，$\Aset$の\'{e}tale covering $\Atmt\twoheadrightarrow \Aset$である．特に，$\Atmt$も局所連結である．
\end{proposition}

\begin{question}
    $\Atmt$のpoint, subtopos, quotient topos, hyperconnected quotient, Aufhebung relation, は何か？
\end{question}
やるべきことだらけ
\end{frame}

\begin{frame}{ここまでのまとめ}
    
\end{frame}
\section[{第三のtopos}]{第三のtopos}
\begin{frame}{いかにして有限性と向き合うか？}
    正則言語の理論には，当然ながら有限性が必須！私は，(Grothendieck) toposと(有限)組み合わせ論は相性が悪いと思い込んでいた．

    \pause

    実は，これがめちゃめちゃうまくいく！
\end{frame}

\begin{frame}{$\ofAset$}
    \begin{definition}[Orbitwise-finite $\A$-set]
        $\A$-set $(Q, \delta\colon Q\times \A\to Q)$が\demph{orbitwise-finite}であるとは，任意の$q\in Q$について$ \{qw\mid w\in \MA\}$が有限であることをいう．Orbitwise-finite automataからなる圏を$\ofAset$と書く．
    \end{definition}

    \begin{theorem}
        $\ofAset$はtopos.
    \end{theorem}
    これは($\Sigma \neq \emptyset$なら)もはやpresheaf toposではない．
\end{frame}

\begin{frame}{余談: 一般論がある}
    
\end{frame}

\begin{frame}{ここまでのまとめ}
    
\end{frame}

\section{第四のtopos}
\section[計算するべきこと]{計算するべき(できる)ことがたくさん！}
\end{document}


\begin{frame}{}

\end{frame}