We define a family fo pgraphs whose the monadic theory is linearly reducible ot the monadic theory S2S of the complete deterministic binary tree .This family contains strictly the ocntext-free graphs investigated by Muller and Schupp, and also the equational graphs defined by Courcelle. using words for vertices, we give a completer set of representatives by prefix rewriting of rational languages. THis subset is a boolean algebra preserved by transitive closure of arcs and by rational restriction on vertices.
展开▼
