Search

# Regular monoidal language

Last updated Jan 14, 2023

Definition. A non-deterministic automaton $(Σ,S,ϕ,i,f)$ is given by a set of symbols $Σ$, a set of states $S$, a pair of initial and final states $i,f ∈ S$, and a transition relation $ϕ_t ⊆ S × S$ for each symbol $t ∈ Σ$. Note that the transition function $ϕ﹕ Σ → Rel(S;S)$ extends to a function $ϕ^\ast ﹕ Σ^\ast → Rel(S;S)$.

A word $w ∈ Σ^{\ast}$ is accepted if there exists a transition to the final state, $f ∈ ϕ^\ast_w(i)$. A regular language is a set of words $L ⊆ Σ^\ast$ that arises as the set of words accepted by an automaton.

Definition (Monoidal regular language). A non-deterministic monoidal automaton $(Γ, S, ϕ,i,f)$ is given by a polygraph of symbols $Γ$, a set of states $S$, a pair of initial and final states $i,f ∈ S$, and a transition relation $ϕ_t ﹕ S^{⊗n} → S^{⊗m}$ for each symbol $t ∈ Γ(n;m)$. Note that the transition function $ϕ_{n,m} ﹕ Γ(n;m) → Rel(S^{⊗n},S^{⊗m})$ extends to a functor $ϕ^{\circledast}﹕ Γ^{\circledast} → Rel_S$.

A word $w ∈ Γ^{\circledast}$ is accepted if there exists a transition to the final state, $f ∈ ϕ^{\circledast}_w(i)$. A monoidal regular language is a set of words that arises as the set of words accepted by a monoidal automaton. References: