A congruence theorem for structured operational semantics of higher-order languages
Karen L. Bernstein · 2002
In this paper we describe the promoted tyft/tyxt rule format for defining higher-order languages. The rule format is a generalization of Groote and Vaandrager's tyft/tyxt format in which terms are allowed as labels on transitions in rules. We prove that bisimulation is a congruence for any language defined in promoted tyft/tyxt format and demonstrate the usefulness of the rule format by presenting promoted tyft/tyxt definitions for the lazy /spl lambda/-calculus, CHOCS and the /spl pi/-calculus.