Houjun Liu

categorical grammar

categorical grammar is a grammar in the language of categories.


  • \(A\), a set of “expressions”
  • \(C\), a set of categories of “syntax”
  • \(\varphi: A \to Pow( C)\), assigning each \(a \in A\) to a set of categories \(c \subset C\)
  • \(G\): a family of sets of n-place operations where \(n=1, 2, \ldots\) (what does a “3-place” op mean? idk)
  • \(R\): a set of rules encoded as tuples: \((f; \{c_1, \dots c_{k}\}; c_{k+1})\), where \(f\) is a \(k\) place operation, and \(c_{j} \in C\)


The operations of this grammar behaves like so:

given a rule \(r \in R\), it tells you that given WLOG an expression in \(c_{1}, c_2, \ldots c_{k} \in C\) (i.e. they were mapped to that set \(\varphi\)), \(f\) will map that set of expressions into the same new category \(c_{k+1}\).

additional information

a basic categorical grammar

one implementation of a basic categorical grammar is as follows: