Tree languages with fixed variables and their algebraic structures

Abstract

Tree languages, sets of terms, have been more widely applied in automata theory and related fields. In this paper, a specific class of tree languages, which induced by terms of a fixed variable, is introduced. Under non-deterministic superposition operations of tree languages, the power clone of tree languages with fixed variables is constructed and some of their properties are investigated. These lead us to propose certain semigroups consisting of the set of tree languages with fixed variables and different binary associative operations.