← Topoi of automata II
main.tex
\documentclass{amsart}
\usepackage[left=2cm, right=2cm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{amsfonts, amsthm, amssymb, mathtools,etoolbox}
\usepackage{blindtext}
\usepackage[colorlinks=true, urlcolor=blue, linkcolor=blue, citecolor=blue]{hyperref}
\usepackage{tikz,tikz-cd}
\usepackage{array}
\usepackage{cleveref}
\usepackage[style=alphabetic,sorting=nyt]{biblatex}
\renewbibmacro{in:}{}
\addbibresource{CommonBiblio20240922.bib}
\tikzset{pullback/.style={minimum size=1.2ex,path picture={
\draw[opacity=1,black,-,#1] (-0.5ex,-0.5ex) -- (0.5ex,-0.5ex) -- (0.5ex,0.5ex);%
}}}
\usetikzlibrary{automata, positioning, calc}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{todo}[theorem]{Todo}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{question}[theorem]{Question}
\newtheorem{idea}[theorem]{Idea}
\newcommand{\dq}[1]{``#1"}
\newcommand{\memo}[1]{\textcolor{red}{memo: #1}}
\newcommand{\invmemo}[1]{\textcolor{blue}{memo: #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{\LC}{\mathbb{L}}
\newcommand{\SQ}{\mathcal{T}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\ob}{\mathrm{ob}}
\newcommand{\op}{\mathrm{op}}
\newcommand{\Set}{\mathbf{Set}}
\newcommand{\FinSet}{\mathbf{FinSet}}
\newcommand{\BoolAlg}{\mathbf{BoolAlg}}
\newcommand{\Cont}{\mathbf{Cont}}
\newcommand{\PSh}{\mathbf{PSh}}
\newcommand{\Sh}{\mathbf{Sh}}
\newcommand{\DFA}{\mathrm{DFA}}
% \newcommand{\DFA}{\mathcal{DFA}\mathrm{}}
\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{\sgt}{\{\cdot\}}
\newcommand{\je}{\mathbf{je}}
\newcommand{\Cl}{\mathrm{Clopen}}
\newcommand{\Gal}{\mathrm{Gal}}
\newcommand{\A}{\Sigma}
\newcommand{\MA}{{{\Sigma}^{\ast}}}
\newcommand{\proMA}{\widehat{\MA}}
\newcommand{\FA}{F_{\A}}
\newcommand{\pFA}{\hat{\FA}}
% \newcommand{\Aset}{\PSh (\MA)}
\newcommand{\Aset}{\A\text{-}\Set}
\newcommand{\T}{2x^{\A}}
% \newcommand{\Atmt}{\T\text{-}\mathbf{Coalg}}
\newcommand{\Atmt}{\mathbf{Atmt}}
% \newcommand{\Lan}{\mathcal{L}\mathrm{ng}}
% \newcommand{\Reg}{\mathcal{R}\mathrm{eg}}
\newcommand{\Lan}{\mathcal{L}}
\newcommand{\Reg}{\mathcal{R}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\Func}[2]{[#1,#2]}
\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}{{\Aset}_{\f}}
\newcommand{\fAset}{\A\text{-}\FinSet}
\newcommand{\ofAset}{{\Aset}_{\of}}
\newcommand{\AFinMon}{\A\text{-}\mathbf{FinMon}}
\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{\demph}[1]{\textit{\textbf{#1}}}
\newcommand{\Geom}{\mathbf{Geom}}
\newcommand{\SigmaInf}{\Sigma^{\leq \omega}}
\font\maljapanese=dmjhira at 2.5ex
\newcommand{\yo}{\textrm{\!\maljapanese\char"48}}
\newcommand{\abs}[1]{\left | #1 \right|}
\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{\Lv}{{Local variety}}
\newcommand{\lv}{{local variety}}
\newcommand{\Lvs}{{Local varieties}}
\newcommand{\lvs}{{local varieties}}
\newcommand{\Dyck}{\mathrm{Dyck}}
\renewcommand{\a}{\texttt{a}}
\renewcommand{\b}{\texttt{b}}
\newcommand{\dep}{\mathbf{d}}
\newcommand{\val}{\mathbf{v}}
\title{Topoi of automata II: Hyperconnected geometric morphisms, syntactic monoids, and language classes}
\author{Ryuya Hora}
\thanks{ZEN University. \url{ryuya_hora@zen.ac.jp}}
% \date{\today}
\subjclass[2020]{18F10, 68Q70, 20M35, 18B20}
\keywords{Automaton, topos, regular language, hyperconnected geometric morphism, coalgebra, finite monoid, profinite word, Myhill-Nerode theorem}
\begin{document}
\begin{abstract}
Hyperconnected geometric morphisms are a topos-theoretic generalization of the notion of surjective monoid homomorphisms. In this paper, we generalize the notion of language recognition by monoid, to arbitrary hyperconnected geometric morphisms from the topos $\Aset$.
Using this, we obtain a construction of a Grothendieck topos $\SQ(C)$ for every language class $C \subset \Pow(\MA)$, which we call the syntactic topos of $C$. For a regular language $L$, the syntactic topos $\SQ(\{L\})$ coincides with the presheaf topos over the syntactic monoid $M_L$. Furthermore, the construction $\SQ$ provides a bijective correspondence between hyperconnected quotients of the topos of regular languages $\ofAset$ and the language classes that is closed under boolean operations and quotients.
\end{abstract}
\maketitle
\tableofcontents
\section{Introduction}
\memo{acknowledgement
Compared to
\cite{gehrke2008duality, adamek2014generalized, ballester2015dual, uramoto2017semi}
}
As we have seen so far, the hyperconnected geometric morphism
\[
\begin{tikzcd}
\Aset \ar[r,"h"] & \ofAset
\end{tikzcd}
\]
plays a central role in our theory of regular languages. This section aims to observe that other hyperconnected geometric morphisms
\[
\begin{tikzcd}
&\E\\
\Aset \ar[r]\ar[ru]\ar[rd] & \F\\
& \mathcal{G}\\
\end{tikzcd}
\]
correspond to other classes of languages.
\section{Hyperconnected geometric morphisms from \texorpdfstring{$\Aset$}{Aset}}
\subsection{Preliminaries 1: Hyperconnected geometric morphism}
See \cite{johnstone2002sketchesv1, johnstone1981factorization} for the detailed definitions of hyperconnected geometric morphisms.
\begin{definition}[Hyperconnected geometric morphisms]
\label{def:hyperconnected}
A geometric morphism $f\colon \E \to \F$ is \demph{hyperconnected} if $f^{\ast}$ is fully faithful and $f$ satisfies the following equivalent conditions:
\begin{itemize}
\item The essential image of $f^{\ast}$ is closed under taking subquotients.
\item The essential image of $f^{\ast}$ is closed under taking subobjects.
\item The essential image of $f^{\ast}$ is closed under taking quotient objects.
\item The counit $\epsilon \colon f^{\ast}f_{\ast} \Rightarrow \id_{\E}$ is monic.
\end{itemize}
\end{definition}
Since $f^{\ast}$ for a hyperconnected geometric morphism $f\colon \E \to \F$ is fully faithful, the codomain topos $\F$ can be regarded as a full subcategory of the domain topos $\E$. If we regard it as a full subcategory, we call it a \demph{hyperconnected quotient}, according to the terminology in \cite[][section VII.]{lawvere2007axiomatic}.
\begin{proposition}
For any Grothendieck topos $\E$, the partially ordered class of (equivalence classes of ) hyperconnected quotients $\HQ(\E)$ is a small complete lattice.
\end{proposition}
\subsection{Preliminaries 2: Local state classifier}
We will recall the description of $\HQ(\E)$ given in \cite{hora2024internal}.
\begin{definition}
We adopt the following definitions:
\begin{itemize}
\item \demph{A local state classifier} of a category $\C$ is the colimit of all monomorphisms
\[
\Xi \coloneqq \colim\left ( \C_{\text{mono}}\to \C \right),
\] where $\C_{mono}$ denotes the subcategory consisting of all objects and all monomorphisms of $\C$.
\item Its associated cocone is denoted by $\{\xi_X\colon X \to \Xi\}_{X\in \ob(\C)}$.
\end{itemize}
\end{definition}
\begin{fact}[\cite{hora2024internal}]
\label{fact:LSCClassification}
For a Grothendieck topos $\E$, we have the following facts:
\begin{itemize}
\item $\E$ has a local state classifier $\Xi$.
\item $\Xi$ admits the canonical $\land$-semilattice structure such that
\[
\begin{tikzcd}
&X\times Y\ar[ld, "\xi_X \times \xi_Y"']\ar[rd, "\xi_{X\times Y}"]&\\
\Xi\times \Xi\ar[rr,"\land"]&&\Xi
\end{tikzcd}
\] commutes for every pair of objects $(X,Y)$.
\item The complete lattice of internal filters of $\Xi$, which is denoted by $\Filt(\Xi)$, is isomorphic to $\HQ(\E)$.
\[
\HQ(\E) \cong \Filt(\Xi)
\]
\item For an internal filter $F\rightarrowtail \Xi$, the counit $\epsilon_X\colon f^* f_* X \rightarrowtail X$ of the associated geometric morphism $f\colon \E \to \F$ is given by the pullback diagram
\[
\begin{tikzcd}
f^* f_* X \ar[r]\ar[d, "\epsilon_X", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F\ar[d,rightarrowtail]\\
X\ar[r, "\xi_X"] &\Xi\\
\end{tikzcd}
\]
\end{itemize}
\end{fact}
From the next subsection, we will specialize this theorem to the topos $\Aset$.
\subsection{The local state classifier of \texorpdfstring{$\Aset$}{Aset}.}
This section describes \demph{the local state classifier} of the topos $\Aset$.
% See \Cref{sssec:LSC} or \cite{hora2024internal} for details.
Automata-theoretically, the local state classifier provides a categorical description of congruences, varieties, and Myhill-Nerode theorem.
% Topos-theoretically, the local state classifier classifies \demph{hyperconnected quotients}., which gives a generalized variety theorem.
\begin{definition}We introduce the notion of right-congruences:
\begin{itemize}
\item A \demph{right congruence} on $\MA$ is an equivalence relation $\sim$ such that for any $u,v,w \in \MA$, if $u\sim v$ then $uw \sim vw$.
\item For two congruences $\sim $ and $ \sim'$, the order relation ${\sim} \leq {\sim'}$ means the condition: for any $u,v \in \MA$, $u\sim v$ implies $u\sim'v$.
\item The poset of all congruences on $\MA$ and their order is denoted by $\Xi$.
\item The action of ${\sim} \ast w$ is defined by $u \mathrel{({\sim} \ast w)} v \iff wu \sim wv$.
\end{itemize}
\end{definition}
\begin{proposition}We have the following properties:
\begin{itemize}
\item Those data amount to make $\Xi$ to be an internal semilattice in the topos $\Aset$. Furthermore, this is the local state classifier \cite{hora2024internal} of the topos $\Aset$.
\item In other words, the $\A$-set $\Xi$ is the colimit of all monomorphisms in $\Aset$.
\item The colimit cocone $\{\xi_{X}\colon X=(Q, \delta)\to \Xi\}_{X\in \ob(\Aset)}$ is given by
\[
w\mathrel{(\xi_X (q))} v \iff qw=qv.
\]
\end{itemize}
\end{proposition}
In particular, the morphism $\xi_{\Lan}\colon \Lan \to \Xi$ captures the notion of Nerode congruence.
\begin{lemma}
\label{lem:NerodeCongruenceAsXi}
The component of the colimit cocone $\xi_{\Lan}\colon \Lan \to \Xi$ sends a language $L$ to \demph{its Nerode congruence} $\sim_{L}$, where
\[
u \sim_{L} v \iff u^{-1}L = v^{-1} L.
\]
\end{lemma}
% This means that the $\A$-set $\Xi$ is the colimit of all monomorphisms in $\Aset$. The colimit cocone will be refered to by $\{\xi_{X}\colon X=(Q, \delta)\to \Xi\}_{X\in \ob(\Aset)}$.
% % To affirmatively answer the question \ref{QuestionInjectivity}, it is enough to answer the following question affirmatively:
% \begin{question}
% Is the function $\xi_{\Lan}$ surjective? In other words, is every congruence induced by a language? \memo{Unless $|\A|<2$, No! Consider an (accessible) automaton (with a start state) with $3$ sinks. At least $2$ of the $3$ sinks define the same language ($\emptyset$ or $\MA$).}
% \end{question}
\begin{proposition}[\cite{hora2024internal} for $\Aset$]
\label{prop:LSCcorresinAset}
There is a bijective correspondence between (equivalence classes of) hyperconnected geometric morphisms from $\Aset$ and the internal filters of $\Xi$, which furthermore correspond to subsets $F \subset \Xi$ such that
\begin{itemize}
\item $F$ is closed under $\MA$-actions,
\[
\forall {\sim}\in F, \forall w\in \MA, ({\sim}*w)\in F.
\]
\item $F$ is closed under taking finite intersections (in particular, $F$ contains the top element), and
\[
\text{(The trivial equivalence)} \in F
\]
\[
\forall {\sim}, {\sim'}\in F, ({\sim}\land {\sim'})\in F.
\]
\item $F$ is upward closed.
\[
\forall{\sim}\in F, \forall \sim'\in \Xi, ({\sim}\leq{\sim'} \implies {\sim'}\in F).
\]
\end{itemize}
\end{proposition}
For a hyperconnected geometric morphism $h\colon \Aset \to \E$, let $F_{h}$ denote the corresponding internal filter of $\Xi$.
\begin{example}
\label{exmp:TheFilterForRegularOrbitFinite}
For the hyperconnected geometric morphism $h\colon \Aset \to \ofAset$, the corresponding filter $F_h$ is the set of all congruences $\sim$ whose quotient set $\MA/{\sim}$ is finite.
\end{example}
% \subsection{Quotient monoids are hyperconnected quotient topoi}
\subsection{Hyperconnected geometric morphisms subsume surjective monoid homomorphisms}
In algebraic language theory, one of the most important objects is surjective monoid homomorphisms $\MA \twoheadrightarrow M$. As every full and bijective on objects functor, any surjective monoid homomorphism $\phi\colon \MA \twoheadrightarrow M$ induces a hyperconnected geometric morphism (\memo{number}\cite{johnstone2002sketchesv1})
% \[
% \ADJ{\Aset=\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(M)}{ {-}\circ \phi}.
% \]
\begin{equation}\label{eq:HyperconnectedQuotientInducedByMonoidSurjection}
\ADJ{\Aset=\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(M).}{ {-}\circ \phi}
\end{equation}
In this section, we will rewrite this hyperconnected quotient in terms of the local state classifier, equivalently, right congruences. Notice that any surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ induces a right congruence
% \[
% u\sim_{\phi} v \iff \phi(u) \sim \phi(v).
% \]
\begin{equation}\label{eq:CongruenceByMonoid}
u\sim_{\phi} v \iff \phi(u) \sim \phi(v).
\end{equation}
Furthermore, this congruence is two-sided in the following sense.
\begin{definition}
A right congruence ${\sim}$ is \demph{a two-sided congruence}, if
\[
u\sim v \implies wuw' \sim wvw'
\]
for any words $u,v,w,w' \in \MA$.
\end{definition}
\begin{lemma}\label{lem:EquivalenceConditionsOfTwoSidedCongruences}
For a right congruence ${\sim} \in \Xi$, the following conditions are equivalent:
\begin{enumerate}
\item $\sim$ is a two-sided congruence.
% , in the sense that
% \[
% v\sim v' \implies uvw \sim uv'w
% \]
% for any words $u,v,v',w \in \MA$.
\item ${\sim}$ is a \demph{congruence of monoid}, in the sense that the quotient set $\MA/ {\sim}$ admits a (necessarily unique) monoid structure such that the quotient map
\[\pi\colon \MA \twoheadrightarrow \MA/{\sim}\]
is a surjective monoid homomorphism.
\item For any word $w\in \MA$, we have ${\sim} \leq (\sim\ast w)\in \Xi$.
\item Its upward closure $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is an internal filter of $\Xi$.
\end{enumerate}
\end{lemma}
\begin{proof}
First, we prove the equivalence between $(1)$ and $(2)$. Assuming $(2)$ and $u \sim v$ (i.e., $\pi(u)=\pi(v)$), we have $\pi(wuw')= \pi(w)\pi(u) \pi(w')=\pi(w)\pi(v) \pi(w') = \pi(wvw')$, which proves $wuw'\sim wvw'$. Conversely, if $\sim$ is a two-sided congruence, then $u\sim v$ and $u'\sim v'$ imply $uu'\sim vu' \sim vv'$, which proves that the well-definedness of the monoid operation on the quotient set $\MA/{\sim}$.
The condition $(3)$ is equivalent to
\begin{align*}
(3) & \iff \forall w\in \MA, \;\forall u,v\in \MA ( {u\sim v} \implies u \mathrel{({\sim}*w)}v)\\
& \iff \forall w,u,v,\; (u\sim v \implies wu\sim wv)\\
&\iff \text{$\sim$ is a left congruence.}
\end{align*}
Since ${\sim}\in \Xi$ is a right congruence, we conclude that the condition $(3)$ is equivalent to $(1)$.
Lastly, we will prove the equivalence between $(3)$ and $(4)$. If $(4)$ holds, then the set $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is closed under the $\MA$-action. Therefore, we have ${\sim}*w \in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ for any $w\in \MA$, which proves $(3)$.
Conversely, we prove that $(3)$ implies $(4)$. Since the upward closure $\{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ is upward closed and closed under finite meets, it suffices to prove that it is closed under the $\MA$-action. For any ${\sim'}\in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$ and $w\in \MA$, we have ${\sim} \leq ({\sim}*w) \leq ({\sim'}*w)$ and hence ${\sim'}*w \in \{{\sim'}\in \Xi\mid {\sim}\leq {\sim'}\}$. This completes the proof.
\end{proof}
Summarizing the above observations, we have the next proposition.
\begin{proposition}[From monoid to topos]
Any surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ induces a hyperconnected geometric morphism from $\Aset$ (Diagram \ref{eq:HyperconnectedQuotientInducedByMonoidSurjection}). Furthermore, the corresponding internal filter $F\subset \Xi$ is given by
% \[
% F = \{{\sim}\in \Xi \mid \forall u,v \in \MA, \phi(u)=\phi(v) \implies u\sim v\},
% \]
% which is
the upward closure of ${\sim_{\phi}}$ (See the notation \ref{eq:CongruenceByMonoid})
\[
F = \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}.
\]
\end{proposition}
\begin{proof}
What we have not yet proven is the equality
\[
F = \{{\sim}\in \Xi \mid \forall u,v \in \MA, \phi(u)=\phi(v) \implies u\sim v\}.
\]
Let us regard the presheaf topos $\PSh(M)$ as a full subcategory of $\Aset$. Then the representable presheaf $M\in \PSh(M)$ is regarded as a $\A$-set $M$ equipped with the canonical action
\[
M\times \MA \to M \colon (m, w) \mapsto m\phi(w).
\]
In particular, we have $\xi_{M}(e)\in F$ for the neutral element $e\in M$. Since we have
\[
u \mathrel{\xi_{M}(e)} v \iff e \phi(u) = e\phi(v)
% \iff \phi(u) = \phi(v)
\iff u \sim_{\phi} v,
\]
we obtain ${\sim_{\phi}} \in F$. Since the internal filter $F$ is upward closed, we conclude an inclusion relation $F \supset \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$.
Conversely, we will prove $F \subset \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$. Since the right hand side, for which we will write $F_{\phi} \coloneqq \{{\sim}\in \Xi \mid {\sim_{\phi}}\leq {\sim}\}$, is an internal filter (\Cref{lem:EquivalenceConditionsOfTwoSidedCongruences}), in order to prove $F\subset F_{\phi}$ it suffices to prove the inclusion relation of the corresponding hyperconnected quotients (assuming the isomorphism of poset given by \Cref{fact:LSCClassification}). \memo{this is rigorously verified by the joint surjectivity...} Take an arbitrary object $(Q, Q \times M \to Q) \in \ob(\PSh(M))$, which will be simply denoted by $Q$ by abuse of notation. What we need to prove is the inequality
\[
{\sim_{\phi}} \leq \xi_{Q}(q) \text{ in } \Xi
\]
for every $q\in Q$,
where $Q$ is regarded as a $\A$-set by $qw\coloneqq q\phi(w)$.
By the Yoneda lemma in the presheaf topos $\PSh(M)$, for each $q\in Q$, we have a unique $M$-set morphism
\[
\begin{tikzcd}
M \ar[r,"\lceil q \rceil"] & Q
\end{tikzcd}
\]
that sends $e\in M$ to $q \in Q$. By regarding them as $\A$-sets, we obtain the diagram
\[
\begin{tikzcd}
M \ar[r,"\lceil q \rceil"] \ar[rd, "\xi_{M}"']& Q\ar[d, "\xi_Q"]\\
&\Xi,
\end{tikzcd}
\]
% we obtain a surjective $M$-set homomorphism
% \[
% \pi\colon \coprod_{q\in Q} M \twoheadrightarrow Q,
% \]
% from the coproduct of the $Q$-copies of the representable $M$-set $M$. Regarding this as a diagram in the topos $\Aset$, for each $q\in Q$, we obtain the diagram
% \[
% \begin{tikzcd}
% M\ar[r, "i_{q}", rightarrowtail]\ar[rrd,"\xi_M"']&
% \coprod_{q\in Q} M
% % \ar[rd, "\xi_{\coprod_{q\in Q} M}"']
% % \ar[rd, "\xi"']
% \ar[r,"\pi", twoheadrightarrow]& Q\ar[d, "\xi_{Q}"]\\
% &&\Xi,
% \end{tikzcd}
% \]
which is not necessarily commutative. Even if it is not commutative, this is lax-commutative, in the sense that $\xi_M \leq \xi_Q \circ \lceil q \rceil$. \memo{cite} Thus, we obtain
\[
{\sim_{\phi}} = \xi_{M}(e) \leq \xi_Q(\lceil q\rceil (e))= \xi_Q (q),
\]
which completes the proof.
\end{proof}
\section{Interaction between hyperconnected quotients and language classes}
% \texorpdfstring{$\mapsto$}{mapsto} language class construction}
\subsection{Topos to language: Hyperconnected geometric morphism recognizes a language}
In this section, we will generalize the notion of language recognition by surjective monoid homomorphisms to arbitrary hyperconnected geometric morphisms.
Recall that a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$ is said to \demph{recognizes} a language $L\in \Lan$ if there exists a subset $S\subset M$ such that $\phi^{-1}(S)=L$.
Since the recognition by hyperconnected quotients has several forms, we will first prove the equivalence between them. We will call this equivalence the Myhill-Nerode theorem for a hyperconnected quotient due to the reason explained in \Cref{rmk:WhyIsItMyhillNerodeTheorem}.
% \subsection{Myhill-Nerode theorem for a hyperconnected geometric morphism}
% The following proposition connects languages and hyperconnected quotient:
\begin{proposition}[Equivalence definitions of recognitions, or the the Myhill-Nerode Theorem]
% for a hyperconnected quotient]
\label{prop:EquivRecognitionOfLnagByHyperconnected}
For a hyperconnected geometric morphism $h\colon \Aset \to \E$ and a language $L\in \Lan$, the following conditions are equivalent:
\begin{enumerate}
\item $L$ is an element of $h^* h_* \Lan \subset \Lan$\footnote{Since the counit $\epsilon_{\Lan}\colon h^* h_* \Lan \rightarrowtail \Lan$ is monic, we can regard it as a subset of $\Lan$.}.
\item The corresponding filter $F_{h}$ contains \text{the Nerode congruence} $\sim_{L}$ of $L$ (\Cref{lem:NerodeCongruenceAsXi}).
% , which is defined by
% \[
% u \sim_{L} v \iff u^{-1}L = v^{-1} L.
% \]
\item There is a $\A$-set $(Q, \delta)$ in the topos $\E$ (regarded as a full subcategory of $\Aset$), such that $(Q, \delta)$ (with a suitable choice of an initial state $q_0$ and accept states $F\subset Q$) recognizes $L$ as an automaton.
\end{enumerate}
\end{proposition}
\begin{proof}
By \Cref{fact:LSCClassification}, we have the following pullback diagram:
\[
\begin{tikzcd}
h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\
\Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\
\end{tikzcd}
\]
This and \Cref{lem:NerodeCongruenceAsXi} prove the equivalence between (1) and (2).
Assuming (1), the counit morphism $\epsilon_{\Lan}\colon h^* h_* \Lan \to \Lan$ itself can be regarded as an automaton (without initial state) (see \memo{cite}). This automaton (with the initial state $L\in h^* h_* \Lan$) recognizes the language $L$. This proves that (1) implies (3).
Lastly, let us assume (3). If a $\A$-set $(Q, \delta)$ recognizes the language $L$, then there is a morphism $\chi_F \colon (Q, \delta) \to \Lan$ such that the image of $\chi_F$ contains $L$. If $(Q, \delta)$ is in $\E$, the universality of the counit implies that there is a lift of $\chi_F$ along the counit:
\[
\begin{tikzcd}
&h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\
(Q, \delta)\ar[ru, dashed]\ar[r, "\chi_F"]&\Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\
\end{tikzcd}
\]
This proves that $L$ is an element of $h^* h_* \Lan$.
\end{proof}
\begin{definition}
We say that a hyperconnected geometric morphism $h\colon \Aset \to \E$ \demph{recognizes} a language $L\in \Lan$, if it satisfies the equivalent conditions of \Cref{prop:EquivRecognitionOfLnagByHyperconnected}.
The set of languages recognized by $h\colon \Aset \to \E$ is denoted by $\LC_{h}$ (or $\LC(\E)$ by the abuse of notation).
\end{definition}
As we have seen, the set $\LC_h$ is in fact a sub$\A$-set $\LC_h = h^* h_* (\Lan) \xrightarrow{\epsilon_{\Lan}} \Lan$, constructed by the pullback diagram
\[
\begin{tikzcd}
\LC_{\Lan}= h^* h_* \Lan \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\
\Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\
\end{tikzcd}
\]
\begin{remark}[Myhill-Nerode theorem]\label{rmk:WhyIsItMyhillNerodeTheorem}
In the case where $\E = \ofAset$, \Cref{prop:EquivRecognitionOfLnagByHyperconnected} is exactly the \demph{Myhill-Nerode theorem}, since the following pullback diagram
\[
\begin{tikzcd}
\Reg \ar[r]\ar[d, "\epsilon_{\Lan}", rightarrowtail]\ar[dr, phantom, "\lrcorner", very near start]&F_{h}\ar[d,rightarrowtail]\\
\Lan\ar[r, "\xi_{\Lan}"] &\Xi.\\
\end{tikzcd}
\]
states that a language $L$ is regular if and only if its Nerode congruence $\sim_L$ has finitely many equivalence classes.
Therefore, we can regard \Cref{prop:EquivRecognitionOfLnagByHyperconnected} as a topos-theoretic generalization of the Myhill-Nerode theorem.
\end{remark}
% In the theory of formal languages, it is central to study \demph{classes of languages}:
% \begin{definition}
% For a hyperconnected geometric morphism $h \colon \Aset \to \E$ from the Grothendieck topos $\Aset$,
% \begin{itemize}
% \item the \demph{associated class of language} is the subobject $\LC_h \coloneqq h^{\ast}h_{\ast} \Lan \rightarrowtail \Lan$ obtained as the component of the counit\footnote{Rigorously, one need to take the strict image of the component of the counit.}.
% \item a language $L$ is \demph{recognized by $h$} if it is an element of (the underlying set of) $L \in \LC_h$.
% \end{itemize}
% \end{definition}
% \begin{definition}
% For a hyperconnected geometric morphism $h\colon \Aset \to \E$, \demph{the associated language class} is the set of languages satisfying the equivalent conditions in \Cref{prop:EquivRecognitionOfLnagByHyperconnected}, which is denoted by $\LC_{h}$.
% \end{definition}
% \begin{definition}
% We say that a hyperconnected geometric morphism $h\colon \Aset \to \E$ \demph{recognizes} a language $L$, if they satisfy the equivalent conditions of \Cref{prop:EquivRecognitionOfLnagByHyperconnected}.
% \end{definition}
\begin{proposition}
For a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow M$,
a language $L$ is recognized by $\phi_*\colon \Aset \twoheadrightarrow \PSh(M)$ if and only if $L$ is recognized by $\phi \colon \MA \twoheadrightarrow M$.
\end{proposition}
Furthermore, for a language $L\in \Lan$, the following conditions are equivalent:
\begin{enumerate}
\item $h$ recognizes $L$, i.e., $L\in \LC(h)$.
\item $\phi$ recognizes $L$.
% Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$.
\item ${\sim} \leq {\sim}_{L}\in \Xi$.
\end{enumerate}
\begin{proposition}
A language $L$ is recognized by $h\colon \Aset \twoheadrightarrow \ofAset$ if and only if $L$ is regular.
\end{proposition}
Combining the above proposition and the main theorem of \cite{hora2024topoi}, we obtain several characterization theorems of regular languages by DFA, finite monoids, and profinite words.
\subsection{Language to topos: The syntactic Grothendieck topos \texorpdfstring{$\SQ(C)$}{SQC} associated with a language class \texorpdfstring{$C$}{C}}
Recall that the syntactic monoid of a language is the minimum monoid (more rigorously, the minimum quotient monoid of $\MA$) that recognizes the language. Similarly, in this section, we will define the syntactic topos $\SQ(C)$ as the minimum topos (more rigorously, minimum hyperconnected quotients) of the topos $\Aset$ that recognizes all languages of a given language class $C$.
\begin{definition}\label{def:LanguageClass}
A \demph{language class} is a subset $C \subset \Lan$ of the set of languages $\Lan$.
% A language class is \demph{quotient-stable} if $\LC$ is a sub $\A$-set of $\Lan$, i.e., if $\forall L\in \LC, \forall w\in \MA, \; w^{-1}L \in \LC$.
% The set of quotient-stable language classes will be denoted by $\qslc$.
\end{definition}
\memo{Before the definition, we make a remark on the order structure of the hyperconnected quotients.}
\begin{definition}\label{def:SyntacticTopos}
For a language class $C\subset \Lan$, its \demph{syntactic Grothendieck topos} $\SQ(C)$ is the minimum hyperconnected quotient that recognizes all languages in $C$.
\end{definition}
By abuse of terminology, for a language $L\in \Lan$, we call $\SQ(\{L\})$ \demph{the syntactic topos of the language $L$}.
% , and write $\SQ(L)$
We write $\SQ(L)$ for $\SQ(\{L\})$ when it does not make any confusion.
\begin{remark}[$\SQ(C)$ is a geometric morphism]
Rigorously speaking, $\SQ(C)$ is not just a topos, but it is a topos equipped with the canonical hyperconnected geometric morphism $h \colon \Aset \twoheadrightarrow \SQ(C)$.
\end{remark}
% The fact that $\LC_h$ is a sub$\A$-set is equivalent to saying that it is quotient-stable:
% \begin{definition}\label{dfn:quotientStable}
% A \demph{language class} is a subset $\LC \subset \Lan$ of the set of languages $\Lan$. A language class is \demph{quotient-stable} if $\LC$ is a sub $\A$-set of $\Lan$, i.e., if $\forall L\in \LC, \forall w\in \MA, \; w^{-1}L \in \LC$.
% The set of quotient-stable language classes will be denoted by $\qslc$.
% \end{definition}
% In order to calculate $\SQ$, l
Let us explicitly write down the construction $\SQ$.
\begin{lemma}
For any family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, there exists
the the minimum internal filter that contains ${\sim}_{\lambda}$ for any $\lambda \in \Lambda$.
\end{lemma}
\begin{proof}
Since an internal filter is defined by several closure properties (\Cref{prop:LSCcorresinAset}), an arbitrary intersection of internal filters is again an internal filter. Therefore, the intersection of all internal filters that contain $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$ is the minimum one.
\end{proof}
\begin{definition}[Generating an internal filter]\label{def:GeneratingFilter}
For a family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, the minimum internal filter that contains them is denoted by
\[
\langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle.
\]
\end{definition}
% \begin{lemma}
For a family of right congruences $\{{\sim}_{\lambda}\}_{\lambda \in \Lambda}$, the generated internal filter $\langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle$ can be explicitly described as
\begin{equation}\label{eq:generatedFilter}
\langle {\sim_{\lambda}}\mid \lambda\in \Lambda\rangle =
\left\{{\sim}\in \Xi
\;\middle |\;
\exists k \geq 0, \; \exists \lambda_1, \dots \lambda_k\in \Lambda,\; \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^k {\sim_{\lambda_{i}}}*w_i\right) \leq {\sim}\right\} .
\end{equation}
% is the minimum internal filter that contains ${\sim}_{\lambda}$ for any $\lambda \in \Lambda$.
% \end{lemma}
% \begin{proof}
% \end{proof}
\begin{proposition}[Concrete description of $\SQ$]\label{prop:concreteDescritionOfSQ}
For a language class $C$, the internal filter $F_{C}\subset \Xi$ corresponding to the hyperconnected quotient $\Aset\twoheadrightarrow \SQ(C)$ is given
% corresponds to the internal filter $F_{C}\subset \Xi$ defined
by
% \[
% F_{C} = \{{\sim} \in \Xi \mid \text{There exists a finite family of languages $L_1 \dots L_k \in C$ and words $w_1, \dots w_n\in \MA$, such that $\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i)*w} \leq {\sim}$}\}
% \]
\[
F_{C} = \langle \xi_{\Lan}(L)\mid L \in C \rangle,
% \left\{{\sim} \in \Xi \;\middle | \;\exists k\in \N, \exists L_1 \dots L_k \in C, \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i)*w_i}\right) \leq {\sim}\right\}.
\]
with the notation in \Cref{def:GeneratingFilter}.
\end{proposition}
\begin{proof}
By \Cref{prop:EquivRecognitionOfLnagByHyperconnected}, the corresponding filter $F_{C}$ should be the
% Let $F_{C}$ be
% the internal filter $F_{C}\subset \Xi$ corresponding to the hyperconnected quotient $\Aset\twoheadrightarrow \SQ(C)$.
the minimum internal filter that contains $\xi_{\Lan}(L)$ for any $L \in C$.
% $F_{\SQ(C)}$ should be the minimum internal filter of $\Xi$ that contains $\xi_{\Lan}(L)$ for every $L \in C$, in other words, $F_{\SQ(C)}$ is the closure of $\{\sim_L \mid L \in C\}$ by the three operations in \Cref{prop:LSCcorresinAset}.
% Such closure must contain $\{\simeq \in \Xi \mid \text{There exists a finite family of languages $L_1 \dots L_k \in C$, such that $\bigwedge_{i=1}^{k} {\sim_{L_i}} \leq {\sim}$}\}$
\end{proof}
Combining \Cref{prop:concreteDescritionOfSQ} and \Cref{eq:generatedFilter}, we obtain the following equation
\begin{equation}\label{eq:TheCorrespondingFilterForALanguageClass}
F_C =\left\{{\sim} \in \Xi \;\middle | \;\exists k\in \N, \exists L_1 \dots L_k \in C, \exists w_1, \dots w_n\in \MA, \left(\bigwedge_{i=1}^{k} {\xi_{\Lan}(L_i*w_i)}\right) \leq {\sim}\right\}.
\end{equation}
\subsection{The construction \texorpdfstring{$\SQ$}{SQ} subsumes syntactic monoids of quasi-regular languages.}
% The Myhill-Nerode theorem states that a language $L$ is regular if and only if its orbit $\{w^{-1}L\mid w\in \MA\}$ is finite. By analogy, we define the regularity of right congruence as follows.
% \begin{definition}
% A right congruence ${\sim}$ is \demph{regular}, if its orbit $\{{\sim}\ast w\mid w\in \MA\}$ is finite.
% \end{definition}
% Notice that if a language $L$ is regular, then its Nerode congruence $\sim_L$ is also regular.
% \begin{remark}
% \memo{Pullback diagram and normalizer operator}
% \end{remark}
\begin{lemma}\label{lem:SufficientAndNecessaryConditionForSyntacticMonoidGivesSyntacticTopos}
For any language $L$, the following conditions are equivalent:
\begin{itemize}
\item The syntatic monoid $M_L$ provides the syntactic topos $\SQ(L)\simeq \PSh(M_L)$
\item There exists a finite family of words $\{w_i\}_{i=1}^n$ such that
\[
{\cong_L} = \bigwedge_{i=1}^n \xi_{\Lan}(L*w_i)
\]
\item There exists a finite family of words $\{w_i\}_{i=1}^n$ such that, for any word $w\in \MA$, we have
\[
\bigwedge_{i=1}^n \xi_{\Lan}(L*w_i) \leq \xi_{\Lan}(L*w).
\]
\end{itemize}
\end{lemma}
\begin{definition}\label{def:quasi-regularLanguages}
A language $L\in \Lan$ is \demph{quasi-regular} if $\xi_{\Xi}(\xi_{\Lan}(L))\in F_{\of}$. \memo{explain $F_{\of}$}
\end{definition}
Let us rewrite this abstract definition. Since we have
\begin{align*}
u \mathrel{\xi_{\Xi}(\xi_{\Lan}(L))} v
&\iff \left(\forall x,y \in \MA, x \mathrel{(\xi_{\Lan}(L)*u)}y \iff x \mathrel{(\xi_{\Lan}(L)*v)}y\right)\\
&\iff \left(\forall x,y \in \MA, ux \mathrel{\xi_{\Lan}(L)}uy \iff vx \mathrel{\xi_{\Lan}(L)}vy\right)\\
&\iff \left(\forall x,y \in \MA, (\forall z_0\in \MA, uxz_0\in L \iff uyz_0\in L) \iff (\forall z_0\in \MA, vxz_1 \in L \iff vyz_1 \in L)\right)\\
\end{align*}
\begin{proposition}
For a language $L$ whose Nerode congruence $\sim_{L}$ is regular (in particular for a regular language), its syntactic quotient $\SQ(L)$ is equal to the one induced by the canonical surjective monoid homomorphism $\MA \twoheadrightarrow M_L$ to the syntactic monoid $M_L$.
\[
\begin{tikzcd}
\SQ(L)\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(M_{L})
\end{tikzcd}
\]
\end{proposition}
\begin{theorem}
If a language $L\in \Lan$ is quasi-regular (\Cref{def:quasi-regularLanguages} $\xi_{\Xi}(\xi_{\Lan}(L))\in F_{\of}$), then $\SQ(L)$ coincides with the presheaf topos over the syntactic monoid $\pi \colon \MA \twoheadrightarrow M_L$
\[
\SQ(L) \simeq \PSh(M_L).
\]
\end{theorem}
\subsection{The prodiscrete Galois monoid $\SQ(C) \simeq \Cont(M_C)$}
This is a prodiscrete version of \cite{uramoto2016semi}.
\begin{conjecture}
According to \cite{rogers2023toposes}, for any language class $C\subset \Lan$, there exists a canonically constructed prodiscrete monoid $M_C$ and a discrete monoid homomorphism $\MA \to M_C$ that induces the hyperconnected geometric morphism
\[
\Aset \twoheadrightarrow \SQ(C).
\]
\end{conjecture}
\subsection{The Galois connection between language recognition and syntactic topos.}
% \subsection{Galois correspondence}
\begin{theorem}\label{thm:GaloisConnection}
This construction $h \mapsto \LC_h$ provides a Galois connection between two complete lattices $\HQ(\Aset)$ and $\qslc$ with a left adjoint which will be denoted by $\SQ$:
% \[
% \ADJ{\HQ(\Aset) \cong \Filt(\Xi)}{\LC = \xi_{\Lan}^{\ast}}{\Sub(\Lan)\cong \qslc}{}.
% \]
% The left adjoint in \Cref{thm:GaloisConnection} will be denoted by $\SQ$.
\[
\ADJ{\HQ(\Aset)}{\LC}{\qslc}{\SQ}.
\]
\end{theorem}
\begin{proof}
We will prove it via the following paraphrase:
\[
\ADJ{\HQ(\Aset) \cong \Filt(\Xi)}{\LC = \xi_{\Lan}^{\ast}}{\Sub(\Lan)\cong \qslc}{}.
\]
Two isomorphisms above are due to \Cref{fact:LSCClassification} and the fact that a language class is quotient-stable if and only if it is a sub$\A$-set of $\Lan$. To prove that the construction $\LC$ has a left adjoint, it is enough to prove that it preserves all infimums. Since the construction $\LC$ is just a pullback along the morphism $\xi_{\Lan}$, the proof is completed.
\end{proof}
Because this is a Galois connection, we automatically obtain the following bijective correspondence between \dq{fixed points.}
\begin{corollary}\label{Cor:TheCorrespondence}
There is a canonical isomorphism between two complete lattices
\[
\Image(\SQ) \cong \Image(\LC).
\]
\end{corollary}
\begin{proof}
This is the equivalence of categories induced by the adjunction \Cref{thm:GaloisConnection}.
\end{proof}
We have reached an abstract viewpoint. In the following subsection, we will observe through concrete examples how these abstract \Cref{thm:GaloisConnection} and \Cref{Cor:TheCorrespondence} subsume some concrete theories of automata.
For a quotient-stable language class $C$, $\SQ(C)$ is a hyperconnected geometric morphism $\Aset \to \E$. However, if it is not confusing, it will be referred to just by the codomain topos $\E$.
\subsection{Examples and calculations of the correspondence}
This subsection aims to give some concrete examples of the correspondence \Cref{thm:GaloisConnection} and \Cref{Cor:TheCorrespondence}.
\para{Toy examples}
Let us see some of the easiest examples.
\begin{example}[Maximum element]
The identity geometric morphism $\id_{\Aset}\colon \Aset \to \Aset$ is the maximum hyperconnected quotient. The associated language class $\LC_{\id_{\Aset}}$ is the set of all languages. Conversely, the hyperconnected quotient $\SQ(\Lan)$ is $\id_{\Aset}$, since there is a language $L$ whose Nerode congruence ${\sim_{L}}$ is trivial \footnote{If $\abs{\A}\leq 1$, it is easy to construct such a language. For the case where $\abs{\A}>1$, see \memo{Exmp:SquareLanguage}.}.
\[
\begin{tikzcd}
\Aset \ar[r, bend right, "\LC"', mapsto ] & \Lan \ar[l, bend right, "\SQ"', mapsto]
\end{tikzcd}
\]
\end{example}
\begin{example}[Minimum element]
Since $\SQ$ is a left adjoint, it sends the empty language class $\{\}$ to the smallest hyperconnected quotient, which is
the global section geometric morphism \[
!\colon \Aset \to \Set.\]
% is hyperconnected.
The corresponding class $\LC_{\Set}$ is the set $\{\emptyset, \MA\}$.
\[
\begin{tikzcd}
&\{\}\ar[ld, "\SQ"', mapsto]\\
\Set \ar[r, bend right, "\LC", mapsto ] & \{\emptyset, \MA\} \ar[l, bend right, "\SQ", mapsto]
\end{tikzcd}
\]
\end{example}
\para{Integers, and profinite integers}
\begin{example}[Regular cases]
For a regular language $L$, its syntactic quotient is given by
\[
\begin{tikzcd}
\SQ(L)\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(M_{L})
\end{tikzcd}
\]
since its Nerode congruence $\sim_L$ is regular. For example, for a positive interger $n>0$, let us consider the (regular) language $L_n \coloneqq \{w\mid \abs{w}_a \cong \abs{w}_b \mod n\}$, where $\abs{w}_\a$ (respectively, $\abs{w}_\b$) denotes the number of $\a$ (respectively $\b$) in the word $w$.
Its Nerode congruence $\sim_{L_n}$ is given by
\[
w\sim_{L_n} w' \iff \abs{w}_a - \abs{w}_b \cong \abs{w'}_a - \abs{w'}_b \mod n,
\]
and
its syntactic quotient is given by
\[
\begin{tikzcd}
\SQ({L_n})\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(\Z/n\Z).
\end{tikzcd}
\]
\end{example}
\begin{example}[Non-regular example]
Let us consider the (non-regular) language $L_0\coloneqq \{w\mid \abs{w}_a = \abs{w}_b\}$, where $\abs{w}_\a$ (respectively, $\abs{w}_\b$) denotes the number of $\a$ (respectively $\b$) in the word $w$. Its Nerode congruence $\sim_{L_0}$ is given by
\[
w\sim_{L_0} w' \iff \abs{w}_a - \abs{w}_b = \abs{w'}_a - \abs{w'}_b,
\]
which is regular, since it is fixed by the word action.
Then, its syntactic quotient is given by
\[
\begin{tikzcd}
\SQ({L_0})\colon \Aset \ar[r, "", twoheadrightarrow] &\PSh(\Z).
\end{tikzcd}
\]
\end{example}
\begin{example}
The geometric morphism $\Aset \to \mathbf{Cont}(\hat{F_{\A}})$ to the topos of continuous actions of the profinite completion of the free group on $\Sigma$ is hyperconnected. The corresponding class is the set of \demph{group languages} (\memo{cite}).
\end{example}
\begin{example}
Similarly, in the case where $\A$ is a singleton, the geometric morphism $\Aset = \sigma\text{-}\Set \to \mathbf{Cont}(\mathbb{Z}_p)$ to the topos of continuous actions of the topological group of $p$-adic integers is hyperconnected. The corresponding class is the set of languages $L$ such that $L$ is periodic and its period is a power of $p$.
\end{example}
\begin{example}
The geometric morphism $\Aset \to \sigma\text{-}\Set = \PSh(\N)$ to the topos of discrete dynamical systems (also known as difference sets), induced by the monoid homomorphism $\MA \to \N\colon w \mapsto (\text{the length of }w)$, is hyperconnected. The corresponding class is the set of \demph{length languages} $L$, which is a language $L$ such that if $w$ and $v$ have the same length and $w \in L$, then $v \in L$.
\end{example}
\begin{example}
The geometric morphism $\Aset \to \Aset_{\mathrm{e.f.}}$ to the topos of eventually fixed $\A$-sets is hyperconnected. The corresponding class is the set of \demph{prefix languages} $L$, which is a language $L$ such that there exists a finite set of words $P$, and a word $w \in \MA$ belongs to $L$ if and only if at least one element of $P$ is a prefix of $w$.
\end{example}
\begin{example}
\cite{lawvere1989display, pin2010mathematical}
\end{example}
\begin{example}
Commutative language
\end{example}
\begin{example}
Lattice
\end{example}
\begin{example}[Syntactic monoid]
\end{example}
\begin{table}[ht]
\centering
\begin{tabular}{c|c}
$\E = \mathrm{cod}(h)$& $\Lan_h$\\ \hline
$\Aset$& $\Lan$\\ \hline
$\ofAset$&$\Reg$\\ \hline
$\mathbf{Cont}(\hat{F_{\A}})$& Group languages\\ \hline
$\sigma\text{-}\Set$ & Length languages\\ \hline
$\Aset_{\mathrm{e.f.}}$&Prefix languages\\ \hline
$\Set$&$\{\emptyset, \A\}$\\
\end{tabular}
\caption{A few examples of associated classes}
\label{TableExampleofHQcorrespondence}
\end{table}
\begin{example}[Regular languages: Profinite words in \cite{pin2010mathematical}, conceptually]
Let $\ofAset$ be a full subcategory of $\Aset$ that consists of orbit-finite automata. Then the embedding $\ofAset\to \Aset$ has a right adjoint, and provides a hyperconnected geometric morphism $q\colon \Aset \to \ofAset$. A language $L$ is a $q$-language if and only if $L$ is regular!
\end{example}
\begin{example}[Group languages]
Let $\pFA$ be the profinite completion of the free group $\FA$, equipped with the canonical profinite topology. Let $\mathrm{Cont}(\pFA)$ be the topos of continuous right $\pFA$ actions (see \cite{maclane1994sheaves}). Then, the dense monoid morphism $\MA \to \pFA$ induces a hyperconnected geometric morphism $q\colon \Aset \to \mathrm{Cont}(\pFA)$. A language $L$ is a $q$-language, if and only if $L$ is a group language.
\end{example}
\begin{conjecture}
The lattice of hyperconnected quotients of $\ofAset$ is isomorphic to the lattice of \lvs of regular languages and finite $\A$-monoids
\end{conjecture}
\appendix
\section{Language theory}
\begin{lemma}
For a regular language $L$, let $(Q, \delta, F, q_0)$ be its
\end{lemma}
\section{The Galois connection between hyperquotients and subalgebras}
% Let $T$ be an equational theory \footnote{or just a functional language}.
\begin{theorem}\label{thm:GaloisConnectionBetweenHQandSubalgebras}
For a Grothendieck topos $\E$, an equational theory $T$, and an $\E$-internal $T$-algebra $A$, we obtain the following Galois connection
\[
\ADJ{\HQ(\Aset)}{}{\Sub_T (A)}{}.
\]
\end{theorem}
\begin{definition}\label{def:PerfectAlgebra}
An internal $T$-algebra $A$ in a Grothendieck topos $\E$ is \demph{perfect}, if the Galois connection in \Cref{thm:GaloisConnectionBetweenHQandSubalgebras} is an equivalence of the complete lattices.
\end{definition}
\begin{example}
Let $K/\Q$ be a finite-dimensional Galois extension of the field $\Q$. Then the field $K$ is an internal $\Q$-algebra in the topos $\PSh(\Gal(K/Q))$. Then, the Galois connection in \Cref{thm:GaloisConnectionBetweenHQandSubalgebras} is the equivalence between the lattice of normal subgroups of $\Gal(K/Q)$ and the lattice of sub-Galois-extensions $K/M/\Q$. This proves that $K \in \PSh(\Gal(K/\Q))$ is perfect. \memo{Similarly, by replacing $\Q$, we can construct perfect $T$-algebra for any finite-group action topos.}
\end{example}
\memo{Perfect algebra seems to be preserved by hyperconnected geometric morphism}
% \section{Characterizing surjective monoid homomorphisms among hyperconnected geometric morphisms}
\section{Surjective monoid homomorphisms are exactly essential and hyperconnected quotients}
\begin{definition}
A geometric morphism
\[
\ADJ{\E}{f_*}{\F}{f^*}
\]
is essential, if $f^*$ has a left adjoint.
\end{definition}
\begin{fact}
A full and bijective-on-objects functor $F\colon \C \to \D$ induces a hyperconnected and essential geometric morphism
\[
\ADJ{\PSh(\C)}{\mathrm{Ran}_{F}}{\PSh(\D)}{ {-}\circ F}.
\]
Furthermore, this construction provides a one-to-one correspondence between
\begin{itemize}
\item (isomorphism classes of) full and bijective-on-objects functors $F\colon \C \to \D$ and
\item
(equivalence classes of) hyperconnected and essential geometric morphisms from $\PSh(\C)$.
\end{itemize}
\end{fact}
\begin{proof}
The first half is easy to prove and well-known. For example, you can find the details in \cite{johnstone2002sketchesv1}.
For the latter, \cite{el2002simultaneously} proves that every essential and connected geometric morphism from $\PSh(\C)$ is induced by a bijective-on-objects (and lax-epi) functor $F\colon \C \to \D$. If the induced essential geometric morphism $\mathrm{Lan}_{F} \dashv {-}\circ F \dashv \mathrm{Ran}_{F}$ is hyperconnected, the unit $\C(-, c) \twoheadrightarrow \mathrm{Lan}_{F}(\C(-,c)) \circ F = \D(F{-}, Fc)$ is epic, which means that $F$ is full.
\end{proof}
\begin{proposition}
There is a one-to-one correspondence between (equivalence classes of)
\begin{enumerate}
\item Hyperconnected and essential geometric morphism $h\colon \Aset \to \E$.
\item Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$.
\item Two-sided congruence ${\sim}\in \Xi$.
\end{enumerate}
% Furthermore, for a language $L\in \Lan$, the following conditions are equivalent:
% \begin{enumerate}
% \item $h$ recognizes $L$, i.e., $L\in \LC(h)$.
% \item $\phi$ recognizes $L$.
% % Surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$.
% \item ${\sim} \leq {\sim}_{L}\in \Xi$.
% \end{enumerate}
\end{proposition}
\begin{remark}[Detail of the correspondence]
Let us clarify the correspondence between them. Between (1) and (2), from (2) a surjective monoid homomorphism $\phi\colon \MA \to N$, the corresponding (1) Hyperconnected and essential geometric morphism is given by
\[
\ADJ{\PSh(\MA)}{\mathrm{Ran}_{\phi}}{\PSh(N)}{ {-}\circ \phi}.
\]
The converse is a little more difficult\footnote{The monoid can be recovered as an endomorphism monoid of the forgetful functor $\E \to \Aset \to \Set$}.
Between (2) and (3), from (2) we can define $w\sim v$ by $\phi(w)=\phi(v)$. The converse construction is just by considering the surjection $\MA \twoheadrightarrow N$.
Between (1) and (3), from (1), the corresponding internal filter $F\subset \Xi$ has a minimum element ${\sim}\in \Xi$. Conversely, for a two-sided congruence ${\sim}$, its upward closure $\{{\sim'}\mid {\sim}\leq {\sim'}\}$ is an internal filter, and the corresponding hyperconnected geometric morphism to $F$, is what we want.
\end{remark}
% In particular, surjective monoid homomorphisms from $\MA$ are in one-to-one correspondence with hyperconnected and essential geometric morphism from $\Aset$.
% \begin{proposition}
% For a hyperconnected geometric morphism $h\colon \Aset\to \E$, the following conditions are equivalent:
% \begin{enumerate}
% \item $h$ is essential
% \item There is a surjective monoid homomorphism $\phi \colon \MA \twoheadrightarrow N$ such that $h$ is (equivalent to) the geometric morphism induced by $\phi$
% \[
% \Aset = \PSh(\MA) \xrightarrow{\phi_{\ast}} \PSh(N).
% \]
% \item The corresponding internal filter $F \subset \Xi$ is principal, in the sense that there is a minimum element ${\sim} \in F$\footnote{This is not equivalent to the existence of the minimal \demph{global} element $1 \to F$, which should be the fixed point of the quotient-action.}.
% % such that ${\sim} \leq {\sim'}$ for every ${\sim'}\in \Xi$
% \end{enumerate}
% \end{proposition}
\section{The Dyck language is not quasi-regular}\memo{Thanks to J\'er\'emie Marqu\`es}
Let $\Dyck$ denote \demph{the Dyck language} for the alphabet $\A=\{\texttt{a,b}\}$, i.e., the language of all well-parenthesized words:
\begin{align*}
\Dyck \coloneqq&\{w\in \MA \mid \text{No prefix of $w$ contains $\b$ more than $\a$, and $w$ has the exactly same number of $\a$ and $\b$}.\}\\
=& \{\empword, \texttt{ab}, \texttt{aabb}, \texttt{abab}, \texttt{aaabbb}, \texttt{aababb}, \texttt{aabbab}, \texttt{abaabb}, \texttt{ababab}, \texttt{aaaabbbb}, \texttt{aaababbb}, \texttt{aaabbabb}, \dots\},
\end{align*}
% \[
% \Dyck\coloneqq\{w\in \MA \mid \text{No prefix of $w$ contains $\b$ more than $\a$, and $w$ has the exactly same number of $\a$ and $\b$}.\}
% \]
% For example, $\Dyck$ contains $\empword, \texttt{ab}, \texttt{aabb}, \texttt{abab}, \texttt{aaabbb}, \texttt{aababb}, \texttt{aabbab}, \texttt{abaabb}, \texttt{ababab}, \texttt{aaaabbbb}, \dots$.
which is alternatively defined as the context-free language generated by
\[
S \to \epsilon\; |\;\texttt{a}S\texttt{b} S,
\]
% It is well known that the number of $\Dyck$-words with length $2n$ is the $n$-th Catalan number.
or as the language recognized by the infinite automaton visualized in \Cref{fig:MinimalAutomatonOfDyck}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[shorten >=1pt, node distance=2cm, on grid, auto]
\node[state, accepting, initial] (c0) {$c_{0,0}$};
\node[state, right=of c0] (c1) {$c_{0,1}$};
\node[state, right=of c1] (c2) {$c_{0,2}$};
\node[state, right=of c2] (c3) {$c_{0,3}$};
\node[state, right=of c3] (c4) {$c_{0,4}$};
\node[state, right=of c4] (c5) {$c_{0,5}$};
\coordinate (dot) at ($(c5)+(2.5,0)$);
\node at (dot) {$\cdots$};
% \node (dots) [right=of c5] {$\cdots$};
\node[state, below=of c0] (c*) {$c_{*}$};
\path[->]
(c0) edge[bend left] node {\a} (c1)
(c1) edge[bend left] node {\b} (c0)
(c1) edge[bend left] node {\a} (c2)
(c2) edge[bend left] node {\b} (c1)
(c2) edge[bend left] node {\a} (c3)
(c3) edge[bend left] node {\b} (c2)
(c3) edge[bend left] node {\a} (c4)
(c4) edge[bend left] node {\b} (c3)
(c4) edge[bend left] node {\a} (c5)
(c5) edge[bend left] node {\b} (c4)
(c0) edge[] node {\b} (c*)
(c*) edge [loop below] node {a,b} (c*)
(c5) edge[bend left] node {\a} ($(c5)+(1.7,0.2)$)
($(c5)+(1.7,-0.2)$) edge[bend left] node {\b} (c5);
\end{tikzpicture}
\caption{The minimal automaton of $\Dyck$}
\label{fig:MinimalAutomatonOfDyck}
\end{figure}
\begin{proposition}
Let us consider two conditions on $\A$-sets $(Q, \delta)$:
\begin{enumerate}
\item $\forall q\in Q,\; q*ab=q$.
\item $\forall q\in Q, \; \exists k\geq 0,\; q*b^k \text{ is a fixed point}$.
\end{enumerate}
Then the topos $\PSh(M_{\Dyck})$ is the category of all $\A$-sets satisfying the condition $(1)$, and the syntactic topos $\SQ(\Dyck)$ is the category of all $\A$-sets satisfying the condition $(1), (2)$. In particular, we have $\SQ(\Dyck) \subsetneq \PSh(\Dyck)$, and $\Dyck$ is not quasi-regular.
\end{proposition}
In order to describe the Nerode congruence $\xi_{\Lan}(\Dyck)$, let us introduce several quantities for words:
\begin{itemize}
\item For a word $w$, the number of $\a$ (respectively $\b$) in $w$ is denoted by $|w|_\a$ (respectively $|w|_\b$).
\item For a word $w\in \MA$, its \demph{value} $\val(w) \in \Z$ is defnied by $\val(w) \coloneqq |w|_\a -|w|_\b$.
\item For a word $w\in \MA$, its \demph{depth} $\dep(w)\in \N$ is defined by the maximal value of $-\val(u)$ among all prefixes $u$ of $w$.
\end{itemize}
For example, the value and depth of a word $w=\texttt{abbabbaaabaaaab}$ is visualized in \Cref{fig:ValueAndDepth}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=0.5,>=stealth]
% Draw grid
\foreach \x in {0,...,14} {
\foreach \y in {-3,...,4} {
\draw[gray!30] (\x,\y) rectangle (\x+1,\y+1);
}
}
\draw[blue, dashed] (0,0) -- (15,0);
% \draw[blue, thick] (6,0) -- (6,-2) node[] {};
% \draw[blue] (6,-2) node[below] {$\dep(w)=2$};
\filldraw[blue] (6,-2) circle (5pt) node[right] {$\dep(w)=2$};
% \draw[blue, thick] (15,0) -- (15,3) node[] {};
% \draw[blue] (15,3) node[right] {$\val(w)=3$};
\filldraw[blue] (15,3) circle (5pt) node[right] {$\val(w)=3$};
% Draw arrows with labels
\draw[->,thick] (0,0) -- (1,1) node[midway, above] {\texttt{a}};
\draw[->,thick] (1,1) -- (2,0) node[midway, below] {\texttt{b}};
\draw[->,thick] (2,0) -- (3,-1) node[midway, below] {\texttt{b}};
\draw[->,thick] (3,-1) -- (4,0) node[midway, above] {\texttt{a}};
\draw[->,thick] (4,0) -- (5,-1) node[midway, below] {\texttt{b}};
\draw[->,thick] (5,-1) -- (6,-2) node[midway, below] {\texttt{b}};
\draw[->,thick] (6,-2) -- (7,-1) node[midway, above] {\texttt{a}};
\draw[->,thick] (7,-1) -- (8,0) node[midway, above] {\texttt{a}};
\draw[->,thick] (8,0) -- (9,1) node[midway, above] {\texttt{a}};
\draw[->,thick] (9,1) -- (10,0) node[midway, below] {\texttt{b}};
\draw[->,thick] (10,0) -- (11,1) node[midway, above] {\texttt{a}};
\draw[->,thick] (11,1) -- (12,2) node[midway, above] {\texttt{a}};
\draw[->,thick] (12,2) -- (13,3) node[midway, above] {\texttt{a}};
\draw[->,thick] (13,3) -- (14,4) node[midway, above] {\texttt{a}};
\draw[->,thick] (14,4) -- (15,3) node[midway, below] {\texttt{b}};
% Draw nodes
\foreach \p in {(0,0),(1,1),(2,0),(3,-1),(4,0),(5,-1),(6,-2),
(7,-1),(8,0),(9,1),(10,0),(11,1),(12,2),(13,3), (14,4), (15,3)} {
\filldraw[black] \p circle (2pt);
}
\end{tikzpicture}
\caption{Value and depth of a word $w=\texttt{abbabbaaabaaaab}$}
\label{fig:ValueAndDepth}
\end{figure}
The definition of the Dyck language is rephrased by
\[\Dyck =\{w\in \MA \mid \val(w)=0, \dep(w)=0\}.\]
The equivalence classes by the Nerode congruence $\xi_{\Lan}(\Dyck)$ are
\begin{align*}
d_{0}=&\{w\in \MA\mid \dep(w)>0\},\\
c_{0,0}=&\{w\in \MA\mid \dep(w)=0, \val(w)=0\},\\
c_{0,1}=&\{w\in \MA\mid \dep(w)=0, \val(w)=1\},\\
c_{0,2}=&\{w\in \MA\mid \dep(w)=0, \val(w)=2\},\\
& \vdots\\
c_{0,n}=&\{w\in \MA\mid \dep(w)=0, \val(w)=n\},\\
& \vdots
\end{align*}
and hence its minimal automaton is given by \Cref{fig:MinimalAutomatonOfDyck}.
If a word $w$ satisfies $\dep(w)>0$, then the congruence $\xi_{\Lan}(\Dyck)*w$ is trivial
\[
\xi_{\Lan}(\Dyck)*w= \top \in \Xi.
\]
If $\dep(w)=0$, then the equivalence classes of the congruence $\xi_{\Lan}(\Dyck)*w$ are described using $k\coloneqq \val(w)\geq 0$ as follows:
\begin{align*}
d_{k}=&\{w\in \MA\mid \dep(w)>k\},\\
c_{k,-k}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=-k\},\\
c_{k,-k+1}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=-k+1\},\\
& \vdots\\
% c_{k,0}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=0\},\\
% c_{k,1}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=1\},\\
% & \vdots\\
c_{k,n}=&\{w\in \MA\mid \dep(w)\leq k, \val(w)=n\},\\
& \vdots
\end{align*}
We write $\sim_k$ for the above congruence, which is visualized as \Cref{fig:ActedcongruenceforKequalFive}.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=0.4]
% fill light blue background where x >= 6 and x+y >= 0 using a trapezoid
\fill[blue!20] (6,-6) -- (6,9.3) -- (9.3,9.3) -- (9.3,-9.3) -- cycle;
\draw (10,10) node[right, blue] {$d_{5}$};
% draw axes
\draw[->] (-1,0) -- (10,0) node[right] {$\dep(w)$};
\draw[->] (0,-9) -- (0,10) node[above] {$\val(w)$};
% fill vertical red strips for each n >= -8 along x=0
\foreach \n in {-5,...,9} {
\pgfmathsetmacro{\xmin}{max(0, -\n)}
\fill[red!20] (5.2, \n+0.2) rectangle (\xmin-0.2, \n-0.2) node[left, red] {$c_{5,\n}$};
}
% draw grid points where x \geq 0 and y \geq -x, within x,y \in [-8,8]
\foreach \x in {0,...,9} {
\foreach \y in {-\x,...,9} {
\fill (\x,\y) circle (3pt);
}
}
\end{tikzpicture}
\caption{The congruence for $k=5$}
\label{fig:ActedcongruenceforKequalFive}
\end{figure}
The syntactic congruence $\cong_\Dyck$ is given by ${\cong_\Dyck}=\bigwedge_{k\geq 0} {\sim_k}$, which is explicitly written down as
\[
u\cong_\Dyck v \iff \text{$\dep(u)=\dep(v)$ and $\val(u)=\val(v)$.}
\]
\memo{cite the paper that describes the syntactic monoid of the Dyck language}
We will prove that $\Dyck$ does not satisfy the equivalent conditions in \Cref{lem:SufficientAndNecessaryConditionForSyntacticMonoidGivesSyntacticTopos} by proving
\[{\cong_\Dyck}<\bigwedge_{k\geq 0}^n {\sim_k}\]
for any $n\geq0$. This follows since we have
\[
u \mathrel{\left (\bigwedge_{k\geq 0}^n {\sim_k}\right )} v \iff (\dep(u),\dep(v)>n) \lor (\dep(u)=\dep(v) \land \val(u)=\val(v)).
\]
\memo{Its syntactic prodiscrete monoid is given by $\MA/{\cong_\Dyck}\sqcup \{b^{\infty}a^{?}\}$, where $b^{\infty}a^{?}$ denotes the formally added absorbing element which has $\{d_k/{\cong_\Dyck}\subset \MA/{\cong_\Dyck}\}_{k\geq 0}$ as a fundamental system of open subsets.}
\printbibliography
\end{document}