Trees associated to inverse monoid presentations

[摘要] A necessary and sufficient condition for a tree to be a Schutzenberger graph of a finite inverse monoid presentation is established. This condition is shown to be decidable for an arbitrary rational tree (being rational is a known necessary condition). It is also proved that it is decidable whether or not an arbitrary rational tree is a Schutzenberger graph of some inverse monoid presentation. (C) 2001 Elsevier Science B.V. All rights reserved.

[发布日期] 2001-12-24