Are there any relation between order-sorted algebra (OSA) and grammars (context-free grammar in particular)?

If I'm not mistaken, according to [1], there is an equivalence between order-sorted and many-sorted algebra (MSA) (they are the same up to an isomorphism), and hence the question may be reformulated between MSA and grammars.

[1] Goguen, Joseph A., and Jose Meseguer. Order-sorted algebra. Oxford University. Computing Laboratory. Programming Research Group, 1989.


1 Answer 1


I find the answer to my own question in [2]:

Let $G = \langle N, \Sigma, P \rangle$ be a context-free grammar. We can make $G$ into a many-sorted algebra by taking $N$ as the set of sorts and

$$ G_{w, n} = \{\, p \in P \,\mid\, p = (n, w') \land \operatorname{nt}(w') = w \,\} $$ as an $N^* \times N$-sorted family ($\operatorname{nt}(\alpha)$ returns the ordered sequence of non-terminal symbols in $\alpha \in (N \cup \Sigma)^*$).

The initial $G$-algebra contains the parse trees for all the derivations in the grammar.

Conversely, if $\Sigma$ is an $S$-sorted operator domain, the initial algebra obtained under the previous construction with the grammar

$$ \hat{\Sigma} = \langle S, \Sigma \cup \{(,)\}, P \rangle\quad P=\{\, (s, \sigma(s_1\cdots s_n)) \,\mid\, \sigma \in\Sigma_{s_1\cdots s_n,s} \,\} $$

is isomorphic to the initial $\Sigma$-algebra.

[2] Goguen, Joseph A., et al. "Initial algebra semantics and continuous algebras." Journal of the ACM (JACM) 24.1 (1977): 68-95.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.