Definition. Compositionality, computability, and complexity › Term rewrite systems (§ 6.1) › Many-sorted term rewrite systems (§ 6.1) [pagin2021-many-sorted-trs]

In a many-sorted term rewrite system, $T_{P}si$ is partitioned into subsets corresponding to sorts, and argument places for operators have sort restrictions; complex terms whose subterms satisfy the sort restrictions are well-sorted (corresponding to grammaticality).