Actions, finite state sets and applications to trees

Abstract

Let M be a monoid acting on a set X; for any x∊X and A⊆X we put x ⁻¹ A = {m∊M/xm∊A}. Call A⊆X finite state if card {x ⁻¹ A/x∊X} <∞.

The finite state subsets of T _Σvia the action T _Σ × P _Σ→T _Σare the recognizable forests (P _Σis the monoid of all Σ-trees with just one leaf labeled by a variable x).

Next we prove that the recognizability of forests is equivalent to the finiteness of a certain “syntactic” monoid A Mezei's-like theorem for trees is established: the finite state subsets of T _Σ × T_г are exactly the finite unions of sets of sets of the form B × C B∊Rec(T _Σ) and C∊Rec(T _г) Another characterization of such relations is given using bimorphisms.

Keywords:

• Monoid-action
• finite state subsets
• L-morphisms