← topoi-automata-slacs2025
main.tex
\documentclass[12pt, portrait,aspectratio=169]{beamer}
\usepackage{tikz}
\usepackage{tikz-cd}
\usepackage{amsmath,amssymb}
\usepackage{mathtools}
\usepackage{pifont}
\usepackage[style=authoryear]{biblatex}
\addbibresource{references.bib}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\newcommand{\dq}[1]{``#1"}
\newcommand{\para}[1]{\paragraph{\textbf{#1}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\mor}{\mathrm{mor}}
\newcommand{\dom}{\mathrm{dom}}
\newcommand{\cod}{\mathrm{cod}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\Func}[2]{[#1,#2]}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\demph}[1]{\textbf{#1}}
\newcommand{\cmark}{\ding{51}}
\newcommand{\xmark}{\ding{55}}
\newcommand{\BoolAlg}{\mathbf{BoolAlg}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\DFA}{\mathrm{DFA}}
\newcommand{\Coalg}{\mathbf{Coalg}}
\newcommand{\G}{\mathbb{G}}
\newcommand{\true}{\mathrm{true}}
\newcommand{\Image}{\mathrm{Im}}
\newcommand{\Nor}{\mathrm{N}}
\newcommand{\Sub}{\mathrm{Sub}}
\newcommand{\SubGrp}{\Sub_{\mathrm{Grp}}}
\newcommand{\sgt}{\{\cdot\}}
\newcommand{\je}{\mathbf{je}}
\newcommand{\Cl}{\mathrm{Clopen}}
\newcommand{\A}{\Sigma}
\newcommand{\MA}{{{\Sigma}^{\ast}}}
\newcommand{\proMA}{\widehat{\MA}}
\newcommand{\FA}{F_{\A}}
\newcommand{\pFA}{\hat{\FA}}
\newcommand{\Aset}{\A\text{-}\Set}
\newcommand{\T}{2x^{\A}}
\newcommand{\Atmt}{\mathbf{Atmt}_{\A}}
\newcommand{\Reg}{\mathbf{Reg}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\Pow}{\mathcal{P}}
\newcommand{\HQ}{\mathrm{HQ}}
\newcommand{\pt}{\mathrm{pt}}
\newcommand{\f}{\mathrm{f.}}
\newcommand{\of}{\mathrm{o.f.}}
\newcommand{\pof}{{p_{\of}}}
\newcommand{\fAtmt}{\Atmt_{\f}}
\newcommand{\ofAtmt}{\Atmt_{\of}}
\newcommand{\fAset}{\A\text{-}\FinSet}
\newcommand{\ofAset}{{\Aset}_{\of}}
\newcommand{\AFinMon}{\A\text{-}\mathbf{FinMon}}
\newcommand{\AFinSet}{\A\text{-}\mathbf{FinSet}}
\newcommand{\empword}{\varepsilon}
\newcommand{\Lsq}{L_{\text{sq}}}
\newcommand{\Cong}{\mathrm{Cong}}
\newcommand{\colim}{\mathrm{colim}}
\newcommand{\Filt}{\mathrm{Filt}}
\newcommand{\bool}{\{\top, \bot\}}
\newcommand{\CoE}{{\int} \hspace{-2pt}}
\newcommand{\CoL}{{\CoE \Lan}}
\newcommand{\qslc}{\mathrm{LC}_{\text{q.s.}}}
\newcommand{\Geom}{\mathbf{Geom}}
\newcommand{\SigmaInf}{\Sigma^{\leq \omega}}
\newcommand{\ADJ}[4]
{
\begin{tikzcd}[ampersand replacement = \&, column sep = small]
{#1}
\ar[rr, shift right=1.3ex, "{#2}"']
\&\perp\&
{#3}
\ar[ll, shift right=1.3ex,"{#4}"']
\end{tikzcd}
}
\newcommand{\SN}{\mathrm{SN}}
\newcommand{\ABA}{\mathrm{ABA}}
\newcommand{\XNi}{\Xi}
\newcommand{\Lan}{\mathbf{Lan}}
\newcommand{\SFL}{\mathbf{SFL}}
\newcommand{\GrpL}{\mathbf{GrpL}}
\newcommand{\mo}[1]{{#1}_{\scalebox{0.6}{\text{mono}}}}
\newcommand{\SQ}{\mathcal{T}}
\newcommand{\LC}{\mathbb{L}}
\newcommand{\End}{\mathrm{End}}
\newcommand{\Int}{\mathrm{Int}}
\newcommand{\bL}{\text{[being a loop]}}
\newcommand{\bN}{\text{[not being a loop]}}
\newcommand{\bV}{\text{[being a vertex]}}
\newcommand{\Species}{\FinSet^{\FinSet_0}}
\newcommand{\symG}[1]{\mathfrak{S}_{#1}}
\newcommand{\Aut}[1]{\mathrm{Aut}_{\Set} (#1)}
\newcommand{\spxi}[1]{\SubGrp{(\Aut{#1})}}
\newcommand{\DirGraph}{\PSh(\rightrightarrows)}
\newcommand{\Gal}{{\pi_1}}
\newtheorem{proposition}{Proposition}
\newtheorem{question}{Question}
\newtheorem{remark}{Remark}
\usetheme{Darmstadt}
\usecolortheme{seahorse}
\setbeamertemplate{items}[default]
\setbeamertemplate{theorems}[default]
\setbeamertemplate{blocks}[default]
\AtBeginSection[]
{
\begin{frame}{Table of Contents}
\tableofcontents[currentsection]
\end{frame}
}
\title{Topoi of automata (SLACS 2025):\\
Local state classifier for automata theory
}
\author{Ryuya Hora}
\institute{University of Tokyo}
\date{31 October, 2025}
\begin{document}
\begin{frame}
\begin{columns}
\begin{column}{0.8 \textwidth}
\titlepage
\end{column}
\begin{column}{0.2\textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/QrcodeForNotes.png}
\begin{center}
Slides (Local state classifier for automata theory)
\end{center}
\end{figure}
\end{column}
\end{columns}
\begin{itemize}
\item \textit{Topoi of automata I} [\cite{hora2024topoi}]
\item\textit{Topoi of automata II} [\cite{hora2025topoiII}]
\item \textit{Internal Parameterization of Hyperconnected Quotients} [\cite{hora2024internal}]
\end{itemize}
\end{frame}
\begin{frame}{Table of Contents}
\tableofcontents
\end{frame}
\section{Introduction}
\begin{frame}{Motivation: Not Generalization, but Geometrization!}
My motivation is neither generalisation nor abstraction.
I want to provide a new geometric method/intuition, just like Grothendieck did to number theory!
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/ToposSubsumesMany.jpeg}
\end{figure}
\end{frame}
\begin{frame}{Naive question: Can we imitate Grothendieck?}
\begin{columns}
\begin{column}{0.2\textwidth}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/portrait-placeholder.pdf}
\end{figure}
\end{column}
\begin{column}{0.8\textwidth}
\begin{itemize}
\item Grothendieck defined \demph{topoi} (sites, and schemes) to introduce infinite/continuous geometric methods into number theory, which is traditionally thought of as a finite/discrete subject.
\pause
\item The theory of automata and regular languages is also (pro)finite/discrete combinatorial theory. Is it possible to introduce infinite/continuous geometric methods into this setting?
\end{itemize}
\pause
\end{column}
\end{columns}
\begin{itemize}
\item Primitive word conjecture $\leftarrow$ Topos-Galois theory
\item Generalized star-height $\leftarrow$ Topos-cohomology
\end{itemize}
\end{frame}
\begin{frame}{Original Motivation: Lawvere's open problems in topos theory}
In 2009, W.Lawvere posed $7$ open problems in topos theory [{\cite{lawvere2025open}}]:
\begin{columns}
\begin{column}{0.5\textwidth}
\begin{itemize}
\item[1] \demph{Quotient Toposes}
{\scriptsize [\cite{kamio2024solution}]}
\item[2] Subqotients and Idempotents
\item[3] Boundaries of classes of models
\item[4] The jump operator on levels within a topos
{\scriptsize [\cite{hora2025lawveresfourthopenproblem}]}
\end{itemize}
\end{column}
\begin{column}{0.5\textwidth}
\begin{itemize}
\item[5] Coverings that admit averaging and microlinearity
\item[6] How strong is the adjointness of fractional exponents?
\item[7] The algebra of time
\end{itemize}
\end{column}
\end{columns}
\hspace{5pt}
I defined \demph{local state classifiers} as a partial solution to the first problem.
Today, I will focus on another point of view.
\end{frame}
\begin{frame}{Today's motivation}
I will try to convey the key idea, and I decided \demph{not to talk about topos theory.}
\begin{itemize}
\item The colimit of all monomorphisms $\Xi$ exists in surprisingly many categories!
\item $\Xi$ is the key to connect category theory and word-congruences.
\item This is a theoretical background of the reason why I started to think about topos-theoretic automata theory.
\end{itemize}
\begin{question}
How can we deal with word-congruences in categorical settings?
\end{question}
\end{frame}
\section{LSCs: Definition}
\begin{frame}{Definition of LSC}
\begin{definition}[local state classifier {[\cite{hora2024internal}]}]
A \demph{local state classifier} $\Xi$ of a category $\C$ is a colimit of all monomorphisms:
\[\Xi = \colim (\mo{\C}\rightarrowtail \C).\]
The associated cocone is referred to as $\{\xi_{X}\colon X \to\Xi\}_{X \in \ob{\C}}$.
\end{definition}
\[
\begin{tikzcd}[column sep =tiny, ampersand replacement = \&]
U\ar[rr,"\iota",rightarrowtail]\ar[rd,"\xi_{U}"']\&\&X\ar[ld,"\xi_{X}"]\\
\&\Xi\&
\end{tikzcd}
\]
\end{frame}
\begin{frame}{Toy Example (1/3): sets}
\begin{example}[$\Set$]
The local state classifier of $\Set$ is the terminal object $\Xi = \{\ast\}$.
\end{example}
Consider an arbitrary cocone $\{\alpha_X : X \to L\}$ of ${\Set}_{\mathrm{inj}}\rightarrowtail \Set$. Then, for any set $X$ and its element $x\in X$, we have
\[
\begin{tikzcd}[column sep =tiny, ampersand replacement = \&]
\{\ast\}\ar[rr,"\text{pick}_x",rightarrowtail]\ar[rd,"\alpha_{\{\ast\}}"']\&\&X\ar[ld,"\alpha_{X}"]\\
\&L\&
\end{tikzcd}
\]
and therefore $\alpha_{X}(x)= \alpha_{\{\ast\}}(\ast)$.
\end{frame}
\begin{frame}{Toy Example (2/3): pointed sets}
What is the local state classifier of the category of pointed sets $\Set_{\ast}$?
\begin{center}
\begin{tikzpicture}
\draw[very thick, black] (-2,0) ellipse (1 and 2);
\filldraw[black] (-2,1.5) circle (0.1);
\filldraw[black] (-2,0.5) circle (0.1);
\filldraw[red] (-2,-0.5) circle (0.1);
\filldraw[black] (-2,-1.5) circle (0.1);
\draw[very thick, black] (2,0) ellipse (1 and 1.5);
\filldraw[red] (2,1) circle (0.1);
\filldraw[black] (2,0) circle (0.1);
\filldraw[black] (2,-1) circle (0.1);
\draw[black, ->, very thick] (-1.8,1.5) -- (1.8,1);
\draw[black, ->, very thick] (-1.8,0.5) -- (1.8,-1);
\draw[red, ->, very thick] (-1.8,-0.5) -- (1.8,1);
\draw[black, ->, very thick] (-1.8,-1.5) -- (1.8,0);
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Toy Example (2/3): pointed sets}
What is the local state classifier of the category of pointed sets $\Set_{\ast}$?
It is
\begin{center}
\begin{tikzpicture}
\draw[very thick, black] (2,0) ellipse (1 and 1);
\draw (2,1) circle(0) node[above]{$\Xi$};
\filldraw[red] (2,0.5) circle (0.1);
\filldraw[black] (2,-0.5) circle (0.1);
\end{tikzpicture}
\end{center}
equipped with ...
\end{frame}
\begin{frame}{Toy Example (2/3): pointed sets}
cocone maps
\begin{center}
\begin{tikzpicture}
\draw[very thick, black] (-2,0) ellipse (1 and 2);
\filldraw[black] (-2,1.5) circle (0.1);
\filldraw[black] (-2,0.5) circle (0.1);
\filldraw[red] (-2,-0.5) circle (0.1);
\filldraw[black] (-2,-1.5) circle (0.1);
\draw[very thick, black] (2,0) ellipse (1 and 1);
\filldraw[red] (2,0.5) circle (0.1);
\filldraw[black] (2,-0.5) circle (0.1);
\draw[black, ->, very thick] (-1.8,1.5) -- (1.8,-0.5);
\draw[black, ->, very thick] (-1.8,0.5) -- (1.8,-0.5);
\draw[red, ->, very thick] (-1.8,-0.5) -- (1.8,0.5);
\draw[black, ->, very thick] (-1.8,-1.5) -- (1.8,-0.5);
\draw (0,2) circle(0) node[above]{$\xi_X$};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Toy Example (3/3): colored sets}
What is the local state classifier of the category of $3$-colored sets $\Set/{\{\text{R,G,B}\}}$?
\begin{center}
\begin{tikzpicture}[scale =0.85]
\draw[very thick, black] (-2,0) ellipse (1 and 2.5);
\filldraw[red] (-2,2) circle (0.1);
\filldraw[green] (-2,1) circle (0.1);
\filldraw[blue] (-2,0) circle (0.1);
\filldraw[red] (-2,-1) circle (0.1);
\filldraw[blue] (-2,-2) circle (0.1);
\draw[very thick, black] (2,0) ellipse (1 and 2);
\filldraw[green] (2,1.5) circle (0.1);
\filldraw[blue] (2,0.5) circle (0.1);
\filldraw[green] (2,-0.5) circle (0.1);
\filldraw[red] (2,-1.5) circle (0.1);
\draw[red, ->, very thick] (-1.8,2) -- (1.8,-1.5);
\draw[green, ->, very thick] (-1.8,1) -- (1.8,-0.5);
\draw[blue, ->, very thick] (-1.8,0) -- (1.8,0.5);
\draw[red, ->, very thick] (-1.8,-1) -- (1.8,-1.5);
\draw[blue, ->, very thick] (-1.8,-2) -- (1.8,0.5);
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Toy Example (3/3): colored sets}
What is the local state classifier of the category of $3$-colored sets $\Set/{\{\text{R,G,B}\}}$?
It is
\begin{center}
\begin{tikzpicture}[scale =0.9]
\draw[very thick, black] (2,0) ellipse (1 and 1.5);
\filldraw[red] (2,1) circle (0.1);
\filldraw[green] (2,0) circle (0.1);
\filldraw[blue] (2,-1) circle (0.1);
\draw (2,1.5) circle(0) node[above]{$\Xi$};
\end{tikzpicture}
\end{center}
equipped with ...
\end{frame}
\begin{frame}{Toy Example (3/3): colored sets}
morphisms that classify elements by their colors.
\begin{center}
\begin{tikzpicture}[scale =0.85]
\draw[very thick, black] (-2,0) ellipse (1 and 2.5);
\filldraw[red] (-2,2) circle (0.1);
\filldraw[green] (-2,1) circle (0.1);
\filldraw[blue] (-2,0) circle (0.1);
\filldraw[red] (-2,-1) circle (0.1);
\filldraw[blue] (-2,-2) circle (0.1);
\draw[very thick, black] (2,0) ellipse (1 and 1.5);
\filldraw[red] (2,1) circle (0.1);
\filldraw[green] (2,0) circle (0.1);
\filldraw[blue] (2,-1) circle (0.1);
\draw[red, ->, very thick] (-1.8,2) -- (1.8,1);
\draw[green, ->, very thick] (-1.8,1) -- (1.8,0);
\draw[blue, ->, very thick] (-1.8,0) -- (1.8,-1);
\draw[red, ->, very thick] (-1.8,-1) -- (1.8,1);
\draw[blue, ->, very thick] (-1.8,-2) -- (1.8,-1);
\draw (0,2) circle(0) node[above]{$\xi_X$};
\end{tikzpicture}
\end{center}
\end{frame}
\begin{frame}{Intuition: why local?}
Let $\{\xi_X \colon X\to \Xi\}_{X\in \ob{\C}}$ be a local state classifier.
\vspace{-20pt}
\begin{columns}
\begin{column}{0.4\textwidth}
\begin{center}
\begin{tikzpicture}[xscale = 1, yscale=0.75]
\small
\draw [black,thick](-2,0-1.5) -- (2,0-1.5) -- (2,-1-1.5) -- (-2,-1-1.5) -- cycle;
\draw (0,-2.5)circle(0) node[below]{$\Xi$};
\draw (0,-2)circle(0) node[right]{\tiny $\xi_X (x)$};
\draw [black, thick] (2,3) ellipse (2.5 and 1.5);
\draw (2,3+1.5)circle(0) node[above]{$X$};
\filldraw [black] (1.5,3.3) circle(0.04);
\draw (1.5,3.3)circle(0) node[above]{\tiny $x$};
\draw [black,thick,->] (2,3-1.6) -- (0.2,0.1-1);
\draw (1+0.5,0.3)circle(0) node[right]{$\xi_X$};
\pause
\draw [black,thick] (-2,3.3) circle (0.5);
\draw (-2,3.3+0.5)circle(0) node[above]{$U$};
\draw [black, dotted, thick] (1.5,3.3) circle (0.5);
\filldraw [black] (-2,3.3) circle(0.04);
\draw (-2,3.3)circle(0) node[above]{\tiny $x$};
\draw [black,thick,>->] (-1.5+0.1,3.3) -- (1-0.1,3.3);
\draw (-0.8,3.3)circle(0) node[above]{$\iota$};
\pause
\draw [black,thick,->] (-2,3.3-0.6) -- (-0.2,0.1-1);
\draw (-1-0.5,1.2)circle(0) node[left]{$\xi_U$};
\draw (0,-2)circle(0) node[]{\tiny $=$};
\draw (0,-2)circle(0) node[left]{\tiny $\xi_U (x)$};
\end{tikzpicture}
\end{center}
\end{column}
\begin{column}{0.4\textwidth}
The value of $\xi_{X}(x)$ can be calculated in arbitraly small neighborhood of $x$.
\end{column}
\end{columns}
\end{frame}
\section{LSCs: More Examples}
\begin{frame}{More Examples (1/4): directed graphs}
What is the local state classifier of the category of directed graphs $\DirGraph$?
\begin{center}
\includegraphics[scale =0.19]{images/Graphs2.png}
\end{center}
\end{frame}
\begin{frame}{More Examples (1/4): directed graphs}
The local state classifier of the topos of directed graphs $\DirGraph$ is given by the \dq{$2$-bouquet.}
\begin{enumerate}
\item $\Xi$ is
$
\begin{tikzcd}[ampersand replacement = \&, scale = 2]
\bullet\ar[loop left,"\bL"]\ar[loop right,"\bN ."]
\end{tikzcd}
$
\item $\xi_X$ detects whether a given edge is a loop or not.
\end{enumerate}
\begin{center}
\includegraphics[scale =0.13]{images/Graphs2.png}
\end{center}
\end{frame}
\begin{frame}{More Examples (2/4): group actions for a group $G$}
What is the local state classifier of $\PSh(G)$?\\
$=$ What is the \dq{local data} for each element of a $G$-set $X \curvearrowleft G$?
\pause
For the category of right $G$-actions $\PSh(G)$ for a group $G$,
\begin{enumerate}
\item $\Xi$ is the set of all subgroups $\SubGrp{(G)}$ (equipped with the conjugate action). % $H \mapsto gHg^{-1}$.
\item $\xi_X$ sends each element $x\in X$ to its stabilizer subgroup.
\end{enumerate}
\end{frame}
\begin{frame}{More Examples (3/4): presheaves}
Let $\C$ be a small category. The local state classifier of the presheaf topos $\PSh{(\C)}$ is the presheaf of quotient objects of representable presheaves:
\[\Xi \colon \C^{\op}\to \Set\colon c \mapsto \{y(c) \twoheadrightarrow C\}\]
\pause
\begin{remark}[Dual similarity with the Subobject classifier]
It is a kind of dual to the subobject classifier, which is the presheaf of subobjects of representable presheaves:
\[\Omega \colon \C^{\op}\to \Set\colon c \mapsto \{y(c) \leftarrowtail C\}\]
\end{remark}
\end{frame}
\begin{frame}{More Examples (4/4): Other categories}
The following categories have LSCs.
\begin{itemize}
\item The category of simplicial sets $\mathbf{sSet}$
\item The topos of Joyal's species $\Species$ (cf. [\cite{fiore2024stabilized}])
\item The category of coalgebraic automata $\Coalg_{\T}=\Atmt$.
\item The Schanuel topos $\Cont(\Aut{\N})\cong \Sh(\mo{\FinSet}^{\op}, J_{\mathrm{at.}})$
\item $\mathbf{Ab}$, $\mathbf{SemiLattice}$, and any other categories of algebras.
\item Any Grothendieck topoi including $\Sh(X)$ for a topological space $X$.
\item Any locally presentable categories, including $\mathbf{Poset}, \mathbf{Cat}, \dots$
\end{itemize}
\end{frame}
\section{Atmt: LSC of \texorpdfstring{$\Aset$}{Aset}}
\begin{frame}{$\A$-sets}
We fix a finite set $\Sigma$.
A \demph{$\A$-set} is a pair $(Q, \delta)$ of a set $Q$ and a function $\delta\colon Q \times \A \to Q$.
\begin{definition}
$\Aset$ is
defined by $\Aset \coloneqq \PSh(\MA)$.
\end{definition}
\begin{figure}
\centering
\includegraphics[width=1\linewidth]{images/Aset.jpeg}
\end{figure}
\end{frame}
\begin{frame}{The $\A$-set of right congruences}
A \demph{right congruence} is an equivalence relation $\sim$ on $\MA$ such that
\[
\forall u,v,w\in \MA,\; u\sim v \implies uw\sim vw.
\]
\begin{definition}[The $\A$-set of right congruences $\XNi$]
\begin{description}
\item[Element] Right congruence
($=$ quotient object of the representable $\MA$.)
\item[$\A$-action] $u \mathrel{{({\sim}*w)}} v \iff wu\sim wv.$
\end{description}
\end{definition}
\end{frame}
\begin{frame}{Right congruences form LSC}
For any $\A$-set $(Q, \delta)$, we define a morphism
\[\xi_{(Q, \delta)} \colon (Q, \delta) \to \Xi\]
by sending $q\in Q$ to the right congruence $\xi_{(Q, \delta)}(q)\in \Xi$:
\[
u \mathrel{\xi_{(Q, \delta)}(q)}v \iff q*u=q*v.
\]
\begin{proposition}[LSC of $\Aset$, Universality of right congruences]
The $\A$-set of right congruences $\Xi$, together with the cocone $\{\xi_{(Q, \delta)}\colon (Q, \delta) \to \XNi\}_{(Q, \delta)\in \ob (\Aset)}$
is the local state classifier of $\Aset$.
\end{proposition}
\end{frame}
\begin{frame}{Toy example of LSC calculation}
\begin{example}[The $\A$-set of languages $\Lan$]
\begin{description}
\item[Element] Language
\item[$\A$-action]
$L * w \coloneqq \{v\in \MA\mid wv\in L\}$ (Brzozowski derivative)
\item[Universality] $\Aset((Q, \delta), \Lan)\cong \Pow(Q)$
\end{description}
\end{example}
What's the cocone component
$
\xi_{\Lan}\colon \Lan \to \Xi$?
\pause
\begin{proposition}[A categorical derivation of Nerode congruence]
For any language $L$, $\xi_{\Lan}(L)$ coincides with the \demph{Nerode congruence} of $L$.
\end{proposition}
$u \mathrel{\xi_{\Lan}(L)} v \iff L*u=L*v \iff\left( \forall w\in \MA \; uw\in L \iff vw\in L\right )$
\end{frame}
\section{Atmt: Covariety of \texorpdfstring{$\Aset$}{Aset}}
\begin{frame}{Idea: $\A$-set classes $\to$ language classes}
From a full subcategory $\F\subset \Aset$ ,
we can consider the \demph{induced language class} $\LC_\F\subset \Lan$.
\[
\LC_{\F}\coloneqq\{L \in \Lan\mid \text{some $\A$-set in $\F$ recognizes $L$} \} .
\]
\begin{example}[regular languages]
$\AFinSet$ is the category of finite $\A$-sets.
$\LC_{\AFinSet}$ is the set of regular languages.
\end{example}
\begin{figure}
\centering
\includegraphics[width=0.7\linewidth]{images/0523Covariety.jpeg}
\end{figure}
\end{frame}
\begin{frame}{Q: What kind of full subcategories should we consider?}
It suffices to consider \demph{nice full subcategories.} but which?
In category theory, we tend to consider reflective subcategories:
\begin{itemize}
\item Subtopoi? ($=$ lex reflective subcat)
\item Birkhoff's HSP varieties? ($=$ subquotient-closed reflective sub)
\item Orthogonality classes?
\end{itemize}
\pause
We need to go the "opposite" direction\footnote{This is the reason why it's related to the open problem of \demph{quotient topoi}.}, coreflective ones!
\end{frame}
\begin{frame}{A: Covariety of $\Aset$}
\begin{definition}[Covariety]
A \demph{covariety}\footnote{This terminology is due to Peter Johnstone.This is defined for any Grothendieck topos.} of $\Aset$ is a full subcategory of $\Aset$ that is closed under
\begin{itemize}
\item subobjects,
\item quotient objects, and
\item coproducts.
\end{itemize}
\end{definition}
Every covariety is \demph{coreflective.}
\begin{lemma}[Covarieties are enough.]
For any full subcategory $\F \subset \Aset$, there exists the minimum covariety $\overline{\F} \subset \Aset$ that contains $\F$. Furthermore, we have $\LC_{\F}=\LC_{\overline{\F}}$.
\end{lemma}
\end{frame}
\begin{frame}{Example: What is $\overline{\AFinSet}$? Orbit-finiteness}
\begin{definition}[$\ofAset$]
A $\A$-set $(Q, \delta\colon Q\times \A \to Q)$ is said to be \demph{orbit-finite} if, for any state $q\in Q$, its orbit $q \MA \coloneqq\{qw \mid w\in \MA\}$ is a finite set.
\end{definition}
Let $\ofAset$ denote the full subcategory of $\Aset$ that consists of all orbit-finite $\A$-sets.
\begin{figure}
\centering
\includegraphics[width=0.55\linewidth]{images/Orbit-finiteness.jpeg}
\end{figure}
\begin{example}
$\overline{\AFinSet}= \ofAset\hookrightarrow \Aset$ is a covariety such that $\LC_{\ofAset}= \Reg$.
\end{example}
\end{frame}
\begin{frame}{covariety classification (1/2)}
But how can we calculate covarieties of $\Aset$? (Even the smallness of the number of them is non-trivial a priori.)
\pause
\begin{columns}
\begin{column}{\textwidth}
\begin{theorem}[Classification of covarieties]
For any Grothendieck topos $\E$, (in particular $\E=\Aset$,) there is a bijective correspondence between
\begin{itemize}
\item covarieties of $\E$, and
\item upward closed\footnote{$\Xi$ admits a unique order structure such that $\xi_X (x)\land \xi_{Y}(y) = \xi_{X\times Y} (x,y)$.} subobjects $U \rightarrowtail\Xi$.
\end{itemize}
\end{theorem}
This theorem reduces the study of covarieties of $\Aset$ to the word combinatorics of congruences $\Xi$.
\end{column}
\end{columns}
\end{frame}
\begin{frame}{covariety classification (2/2)}
For a given upward closed subobject $U \rightarrowtail \Xi$, the corresponding covariety $\F_{U}$ is given by
\[
\ob(\F_U)\coloneqq \left \{ X\in \ob(\E)\;\middle |
\begin{tikzcd}[ampersand replacement = \&]
\& U\ar[d, rightarrowtail]\\
X\ar[r,"\xi_X"']\ar[ru, dashed, "\exists"]\&\XNi
\end{tikzcd}
\right \}.
\]
\begin{example}[$\ofAset \xleftrightarrow{\textrm{corresponding}} U_{\of}$ ]
The covariety $\ofAset$ corresponds to the subobject
$U_{\of}\coloneqq \{{\sim}\in \Xi \mid \MA/{\sim}\text{ is finite}\}$.
\end{example}
\end{frame}
\begin{frame}[shrink]{What I cannot talk: Other examples of calculation with LSC}
\small
$\Xi$ translates abstract definitions into concrete word combinatorics:
\begin{itemize}
\pause
\item \demph{Myhill-Nerode theorem} $\LC_{\F}=\xi_{\Lan}^{-1} (U)$ for each covariety $\F$.
\begin{itemize}
\item $\LC_{\ofAset}= \xi_{\Lan}^{-1}( U_{\of}) $ (cf. $\xi_{\Lan}\colon \Lan \to \Xi$ is the nerode congruence.)
\end{itemize}
\pause
\item \demph{Syntactic congruence} ${\cong_L} = \bigwedge_{w\in \MA} \left (\xi_{\Lan}(L)*w\right )$ in $\Xi$.
\begin{itemize}
\item
We need $\xi_{\Xi}\colon \Xi \to \Xi$ to capture the behavior of $\xi_{\Lan}(L)$.
\end{itemize}
\pause
\item \demph{Syntactic monoids} $\Gal(C)$.
\begin{itemize}
\item Prodiscrete for arbitrary $C$: \alert{work in progress; not established}.
\item $\Gal(\Reg)=\proMA$: the profinite monoid of profinite words
\item
$\Gal(\{L\}) = \MA/{\cong_L} \impliedby \xi_{\Xi}(\xi_{\Lan}(L))\in U_{\of} \impliedby\xi_{\Lan}(L) \in U_{\of}$
\end{itemize}
\item \demph{Dyck example} \alert{(work in progress; not established)}:\newline
$\Gal(\{\textrm{well-parenthesized}\})=\langle a,b\mid ab=1\rangle\sqcup \{*\}$ with a non-trivial topology.
\pause
\item \demph{Syntactic topos} $\SQ_C$ for each $C\subset \Lan$.
\begin{itemize}
\item Classification of hyperconnected quotient topoi ($=$ covarieties closed under finite products){\scriptsize [\cite{hora2024internal}]}
\item \alert{Work in progress; not established:} $\SQ_C \simeq \Cont(\Gal(C))$\newline (semi-Galois theory; cf. [\cite{uramoto2025semi}]).
\end{itemize}
\end{itemize}
\end{frame}
\begin{frame}[shrink]{References}
\IfFileExists{\jobname.bbl}{\printbibliography}{\strut}
\end{frame}
\end{document}
\end{document}