Axiomatizing the equational theory of regular tree languages

摘要

We show that a finite set of equation schemes together with the least fixed point rule gives a complete axiomatization of the valid identities of regular tree languages. This result is a generalization of Kozen's axiomatization of the equational theory of regular word languages.