duaLab

Sigma-set

Contents

1. Definition

Fix a finite alphabet $\Sigma$, and let $\Sigma^*$ be the free monoid of words. A $\Sigma$-set is a set $Q$ with a transition function $\delta:Q\times\Sigma\to Q$, that is, a right action of $\Sigma^*$. Morphisms are equivariant maps.

A $\Sigma$-set is orbit-finite if the orbit $\{q\cdot w\mid w\in\Sigma^*\}$ of every state is finite. The state set itself may be infinite. See Definitions 2.1 and 2.17.

2. Examples

The set of languages $\mathcal L=\mathcal P(\Sigma^*)$ is a $\Sigma$-set, with action

$$L\cdot a=\{w\in\Sigma^*\mid aw\in L\}.$$

Here $a\in\Sigma$ and $L$ is a language. Its orbit-finite part consists exactly of the regular languages. See Definition 2.4 and Lemma 2.22.

3. Properties

Proposition 3.1 (Two topoi of states)★

The category of $\Sigma$-sets is the presheaf topos of right $\Sigma^*$-actions. The full subcategory of orbit-finite $\Sigma$-sets is also a Grothendieck topos and is a hyperconnected quotient of it.

See Propositions 2.2 and 2.19.

5. References