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

DOI:
https://doi.org/10.1090/S0002-9947-1993-1073775-X

MathSciNet review:
1073775

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper is concerned with a study of inverse monoids presented by a set subject to relations of the form , , where and are Dyck words, i.e. idempotents of the free inverse monoid on . 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 . 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.

**[1]**J. Barwise,*Handbook of mathematical logic*, North-Holland, 1977. MR**516928 (81d:03037)****[2]**J. Berstel,*Transductions and context-free languages*, Teubner, Studienbücher, 1979. MR**549481 (80j:68056)****[3]**J. C. Birget, S. W. Margolis, and J. C. Meakin,*The word problem for inverse monoids presented by one idempotent relator*, Theoret. Comp. Sci. (to appear). MR**1256202 (94j:20057)****[4]**J. E. Hopcroft and J. D. Ullman,*Formal languages and their relation to automata*, Addison-Wesley, 1969. MR**0237243 (38:5533)****[5]**G. Lallement,*Semigroups and combinatorial applications*, Wiley, 1979. MR**530552 (81j:20082)****[6]**S. W. Margolis and J. Meakin, -*unitary inverse monoids and the Cayley graph of a group presentation*, J. Pure Appl. Algebra**58**(1989), 45-76. MR**996174 (90f:20096)****[7]**D. E. Muller and P. E. Schupp,*The theory of ends, pushdown automata, and second-order logic*, Theoret. Comput. Sci.**37**(1985), 51-75. MR**796313 (87h:03014)****[8]**W. D. Munn,*Free inverse semigroups*, Proc. London Math. Soc.**30**(1974), 385-404. MR**0360881 (50:13328)****[9]**M. Petrich,*Inverse semigroups*, Wiley, 1984. MR**752899 (85k:20001)****[10]**M. O. Rabin,*Decidability of second order theories and automata on infinite trees*, Trans. Amer. Math. Soc.**141**(1969), 1-35. MR**0246760 (40:30)****[11]**-,*Automata on infinite objects and Church's problem*, CBMS Regional Conf. Ser. in Math., no. 14, Amer. Math. Soc., Providence, R.I., 1971.**[12]**H. E. Scheiblich,*Free inverse semigroups*, Proc. Amer. Math. Soc.**38**(1973), 1-7. MR**0310093 (46:9196)****[13]**J.-P. Serre,*Trees*, Springer-Verlag, Berlin and New York, 1980. MR**607504 (82c:20083)****[14]**J. Stallings,*Topology of finite graphs*, Invent. Math.**71**(1983), 551-565. MR**695906 (85m:05037a)****[15]**J. B. Stephen,*Presentations of inverse monoids*, J. Pure Appl. Algebra**63**(1990), 81-112. MR**1037695 (91g:20083)**

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

Retrieve articles in all journals with MSC: 20M05

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1993-1073775-X

Article copyright:
© Copyright 1993
American Mathematical Society