duaLab

Boolean-ringed topos of regular languages

Contents

1. Definition

A Boolean-ringed topos is a Grothendieck topos with an internal Boolean algebra; compare ringed topos.

Fix a finite alphabet $\Sigma$. Let $\mathcal E_{\mathrm{of}}$ be the topos of orbit-finite Sigma-sets, and let $\mathcal R$ be its object of regular languages, with the usual Boolean operations. The Boolean-ringed topos of regular languages is $(\mathcal E_{\mathrm{of}},\mathcal R)$.

See Definitions 3.1–3.2.

2. Properties

Proposition 2.1 (Canonical Boolean algebra)★

The Boolean algebra $\mathcal R$ is the direct image of the two-element Boolean algebra along the canonical point of $\mathcal E_{\mathrm{of}}$.

See Proposition 2.24.

Theorem 2.2 (Four presentations)★

The following descriptions give equivalent Boolean-ringed topoi:

  • orbit-finite $\Sigma$-sets with their canonical Boolean algebra;
  • sheaves on finite $\Sigma$-sets with the sheaf assigning to a state set its subsets;
  • sheaves on finite $\Sigma$-monoids, with equivariant maps of their underlying $\Sigma$-sets, and the sheaf of subsets;
  • continuous actions of the free profinite monoid with its Boolean algebra of clopen subsets.

The two sheaf sites use the topologies generated by jointly surjective families. These presentations express the Myhill–Nerode, finite-automaton, finite-monoid and profinite-word descriptions of regular languages.

See Theorem 3.19 and §§3.2–3.4.

4. References