Inverse monoids, trees and context-free languages
HTML articles powered by AMS MathViewer
- by Stuart W. Margolis and John C. Meakin PDF
- Trans. Amer. Math. Soc. 335 (1993), 259-276 Request permission
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
- Jon Barwise, Monotone quantifiers and admissible sets, Generalized recursion theory, II (Proc. Second Sympos., Univ. Oslo, Oslo, 1977) Studies in Logic and the Foundations of Mathematics, vol. 94, North-Holland, Amsterdam-New York, 1978, pp. 1–38. MR 516928
- Jean Berstel, Transductions and context-free languages, Leitfäden der Angewandten Mathematik und Mechanik [Guides to Applied Mathematics and Mechanics], vol. 38, B. G. Teubner, Stuttgart, 1979. MR 549481, DOI 10.1007/978-3-663-09367-1
- Jean-Camille Birget, Stuart W. Margolis, and John C. Meakin, The word problem for inverse monoids presented by one idempotent relator, Theoret. Comput. Sci. 123 (1994), no. 2, 273–289. MR 1256202, DOI 10.1016/0304-3975(92)00063-W
- John E. Hopcroft and Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0237243
- Gérard Lallement, Semigroups and combinatorial applications, Pure and Applied Mathematics, John Wiley & Sons, New York-Chichester-Brisbane, 1979. MR 530552
- Stuart W. Margolis and John C. Meakin, $E$-unitary inverse monoids and the Cayley graph of a group presentation, J. Pure Appl. Algebra 58 (1989), no. 1, 45–76. MR 996174, DOI 10.1016/0022-4049(89)90052-2
- David E. Muller and Paul E. Schupp, The theory of ends, pushdown automata, and second-order logic, Theoret. Comput. Sci. 37 (1985), no. 1, 51–75. MR 796313, DOI 10.1016/0304-3975(85)90087-8
- W. D. Munn, Free inverse semigroups, Proc. London Math. Soc. (3) 29 (1974), 385–404. MR 360881, DOI 10.1112/plms/s3-29.3.385
- Mario Petrich, Inverse semigroups, Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New York, 1984. A Wiley-Interscience Publication. MR 752899
- Michael O. Rabin, Decidability of second-order theories and automata on infinite trees, Trans. Amer. Math. Soc. 141 (1969), 1–35. MR 246760, DOI 10.1090/S0002-9947-1969-0246760-1 —, Automata on infinite objects and Church’s problem, CBMS Regional Conf. Ser. in Math., no. 14, Amer. Math. Soc., Providence, R.I., 1971.
- H. E. Scheiblich, Free inverse semigroups, Proc. Amer. Math. Soc. 38 (1973), 1–7. MR 310093, DOI 10.1090/S0002-9939-1973-0310093-1
- Jean-Pierre Serre, Trees, Springer-Verlag, Berlin-New York, 1980. Translated from the French by John Stillwell. MR 607504, DOI 10.1007/978-3-642-61856-7
- John R. Stallings, Topology of finite graphs, Invent. Math. 71 (1983), no. 3, 551–565. MR 695906, DOI 10.1007/BF02095993
- J. B. Stephen, Presentations of inverse monoids, J. Pure Appl. Algebra 63 (1990), no. 1, 81–112. MR 1037695, DOI 10.1016/0022-4049(90)90057-O
Additional Information
- © Copyright 1993 American Mathematical Society
- 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