Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Inverse monoids, trees and context-free languages

Authors: Stuart W. Margolis and John C. Meakin
Journal: Trans. Amer. Math. Soc. 335 (1993), 259-276
MSC: Primary 20M05
MathSciNet review: 1073775
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is concerned with a study of inverse monoids presented by a set $ X$ subject to relations of the form $ {e_i} = {f_i}$, $ i \in I$, where $ {e_i}$ and $ {f_i}$ are Dyck words, i.e. idempotents of the free inverse monoid on $ X$. Some general results of Stephen are used to reduce the word problem for such a presentation to the membership problem for a certain subtree of the Cayley graph of the free group on $ X$. In the finitely presented case the word problem is solved by using Rabin's theorem on the second order monadic logic of the infinite binary tree. Some connections with the theory of rational subsets of the free group and the theory of context-free languages are explored.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 20M05

Retrieve articles in all journals with MSC: 20M05

Additional Information

Article copyright: © Copyright 1993 American Mathematical Society