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.


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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.