On the word problem for weakly compressible monoids

References

• Adian, S. I. (1960). The problem of identity in associative systems of a special form. Soviet Math. Dokl. 1:1360–1363.
   Google Scholar
• Adian, S. I. (1966). Defining relations and algorithmic problems for groups and semigroups. Proceedings of the Steklov Institute of Mathematics, No. 85.
   Google Scholar
• Adian, S. I., Oganesian, G. U. (1978). On problems of equality and divisibility in semigroups with a single defining relation. Math. USSR, Izv. 12:207–212. [Izv. Akad. Nauk SSSR Ser. Mat. 42(2)].
   Web of Science ®Google Scholar
• Aho, A. V. (1968). Indexed grammars—an extension of context-free grammars. J. Assoc. Comput. Mach. 15: 647–671. DOI: 10.1145/321479.321488.
   Web of Science ®Google Scholar
• An i¯s i¯mov, A. V. (1971). The group languages. Kibernetika (Kiev) 4:18–24.
   Google Scholar
• Berstel, J., Perrin, D. (1985). Theory of Codes, volume 117 of Pure and Applied Mathematics. Orlando, FL: Academic Press, Inc.
   Google Scholar
• Book, R. V., Jantzen, M., Wrathall, C. (1982). Monadic Thue systems. Theoret. Comput. Sci. 19(3):231–251. DOI: 10.1016/0304-3975(82)90036-6.
   Web of Science ®Google Scholar
• Book, R. V., Otto, F. (1993). String-Rewriting Systems. Texts and Monographs in Computer Science. New York: Springer-Verlag.
   Google Scholar
• Brough, T., Cain, A. J., Pfeiffer, M. (2019). Context-free word problem semigroups. In: Hofman, P., Skrzypczak, M., eds. Developments in Language Theory, volume 11647 of Lecture Notes in Computer Science. Cham: Springer, pp. 292–305.
   Google Scholar
• Campbell, C. M., Robertson, E. F., Ruškuc, N., Thomas, R. M. (1995). Semigroup and group presentations. Bull. London Math. Soc. 27(1):46–50. DOI: 10.1112/blms/27.1.46.
   Google Scholar
• Duncan, A., Gilman, R. H. (2004). Word hyperbolic semigroups. Math. Proc. Cambridge Philos. Soc. 136(3): 513–524. DOI: 10.1017/S0305004103007497.
   Google Scholar
• Dunwoody, M. J. (1985). The accessibility of finitely presented groups. Invent. Math. 81(3):449–457. DOI: 10.1007/BF01388581.
   Web of Science ®Google Scholar
• Engelfriet, J. (1985). Hierarchies of hyper-AFLs. J. Comput. System Sci. 30(1):86–115. DOI: 10.1016/0022-0000(85)90006-6.
   Web of Science ®Google Scholar
• Gray, R. D., Steinberg, B. (2022). A Lyndon’s identity theorem for one-relator monoids. Selecta Math. (N.S.) 28(3):Paper No. 59, 53.
   Web of Science ®Google Scholar
• Greibach, S. A. (1970). Full AFLs and nested iterated substitution. Inf. Control 16:7–35.
   Google Scholar
• Harrison, M. A. (1978). Introduction to Formal Language Theory. Reading, MA: Addison-Wesley Publishing Co.
   Google Scholar
• Hoffmann, M., Holt, D. F., Owens, M. D., Thomas, R. M. (2012). Semigroups with a context-free word problem. In: Yen, H.-C., Ibarra, O. H., eds. Developments in Language Theory, volume 7410 of Lecture Notes in Computer Science. Heidelberg: Springer, pp. 97–108.
   Google Scholar
• Holt, D. F., Owens, M. D., Thomas, R. M. (2008). Groups and semigroups with a one-counter word problem. J. Aust. Math. Soc. 85(2):197–209. DOI: 10.1017/S1446788708000864.
   Web of Science ®Google Scholar
• Hopcroft, J. E., Ullman, J. D. (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Series in Computer Science. Reading, MA: Addison-Wesley Publishing Co.
   Google Scholar
• Howie, J. M. (1995). Fundamentals of Semigroup Theory, volume 12 of London Mathematical Society Monographs. New Series. New York: The Clarendon Press, Oxford University Press, Oxford Science Publications.
   Google Scholar
• Jantzen, M. (1988). Confluent String Rewriting, volume 14 of EATCS Monographs on Theoretical Computer Science. Berlin: Springer-Verlag.
   Google Scholar
• Kobayashi, Y. (2000). Finite homotopy bases of one-relator monoids. J. Algebra 229(2):547–569. DOI: 10.1006/jabr.1999.8251.
   Web of Science ®Google Scholar
• Král, J. (1970). A modification of a substitution theorem and some necessary and sufficient conditions for sets to be context-free. Math. Systems Theory 4:129–139. DOI: 10.1007/BF01691097.
   Google Scholar
• Lallement, G. (1974). On monoids presented by a single relation. J. Algebra 32:370–388. DOI: 10.1016/0021-8693(74)90146-X.
   Web of Science ®Google Scholar
• Lyndon, R. C., Schupp, P. E. (1977). Combinatorial Group Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89. Berlin-New York: Springer-Verlag.
   Google Scholar
• Magnus, W. (1932). Das Identitätsproblem für Gruppen mit einer definierenden Relation. Math. Ann. 106(1): 295–307. DOI: 10.1007/BF01455888.
   Google Scholar
• Magnus, W., Karrass, A., Solitar, D. (1966). Combinatorial Group Theory: Presentations of Groups in Terms of Generators and Relations. New York-London-Sydney: Interscience Publishers [John Wiley & Sons, Inc.].
   Google Scholar
• Makanin, G. S. (1966). On the identity problem for finitely presented groups and semigroups. PhD thesis, Steklov Mathematical Institute, Moscow.
   Google Scholar
• Makanin, G. S. (1966). On the identity problem in finitely defined semigroups. Dokl. Akad. Nauk SSSR 171: 285–287.
   Google Scholar
• Malheiro, A. (2005). Complete rewriting systems for codified submonoids. Int. J. Algebra Comput. 15(2):207–216. DOI: 10.1142/S0218196705002220.
   Web of Science ®Google Scholar
• Markov, A. A. (1947). On certain insoluble problems concerning matrices. Doklady Akad. Nauk SSSR (N. S.) 57: 539–542.
   Google Scholar
• Muller, D. E., Schupp, P. E. (1983). Groups, the theory of ends, and context-free languages. J. Comput. System Sci. 26(3):295–310. DOI: 10.1016/0022-0000(83)90003-X.
   Web of Science ®Google Scholar
• Nyberg-Brodda, C.-F. (2021). A translation of G. S. Makanin’s 1966 Ph.D. thesis “On the Identity Problem for Finitely Presented Groups and Semigroups”. Available online at arXiv:2102.00745.
   Google Scholar
• Nyberg-Brodda, C.-F. (2021). The word problem and combinatorial methods for groups and semigroups. PhD thesis, University of East Anglia, UK.
   Google Scholar
• Nyberg-Brodda, C.-F. (2021). The word problem for one-relation monoids: a survey. Semigroup Forum 103(2): 297–355. DOI: 10.1007/s00233-021-10216-8.
   Web of Science ®Google Scholar
• Nyberg-Brodda, C.-F. (2022). On the word problem for special monoids. Semigroup Forum 105(1):295–327. DOI: 10.1007/s00233-022-10286-2.
   Web of Science ®Google Scholar
• Nyberg-Brodda, C.-F. (2023). On the word problem for free products of semigroups and monoids. J. Algebra 622:721–741. DOI: 10.1016/j.jalgebra.2023.02.007.
   Web of Science ®Google Scholar
• Post, E. L. (1947). Recursive unsolvability of a problem of Thue. J. Symbolic Logic 12:1–11. DOI: 10.2307/2267170.
   Google Scholar
• Thue, A. (1914). Problem über Veränderungen von Zeichenreihen nach gegebenen Regeln. Christiana Videnskaps-Selskabs Skrifter, I. Math. naturv. Klasse, 10.
   Google Scholar
• Zhang, L. (1992). Congruential languages specified by special string-rewriting systems. In: Ito, M., ed. Words, Languages and Combinatorics (Kyoto, 1990). River Edge, NJ: World Scientific Publishing, pp. 551–563.
   Google Scholar
• Zhang, L. (1992). On the conjugacy problem for one-relator monoids with elements of finite order. Int. J. Algebra Comput. 2(2):209–220. DOI: 10.1142/S021819679200013X.
   Google Scholar