Inverse monoids, trees and context-free languages

Margolis, Stuart W.; Meakin, John C.

doi:10.1090/S0002-9947-1993-1073775-X

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

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