Abstract
This paper studies the classes of semigoups and monoids with context-free and deterministic context-free word problem. First, some examples are exhibited to clarify the relationship between these classes and their connection with the notions of word-hyperbolicity and automaticity. Second, a study is made of whether these classes are closed under applying certain semigroup constructions, including direct products and free products, or under regressing from the results of such constructions to the original semigroup(s) or monoid(s).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Book, R.V., Otto, F.: String Rewriting Systems. Texts and Monographs in Computer Science. Springer, New York (1993). https://doi.org/10.1007/978-1-4613-9771-7
Brough, T.: Groups with poly-context-free word problem. Groups Complex. Cryptol. 6(1), 9–29 (2014). https://doi.org/10.1515/gcc-2014-0002
Brough, T.: Word problem languages for free inverse monoids. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 24–36. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94631-3_3
Brough, T., Cain, A.J.: A language hierarchy of binary relations (2018)
Brough, T.R.: Groups with poly-context-free word problem. Ph.D. thesis, University of Warwick (2010). https://wrap.warwick.ac.uk/35716/
Cain, A.J., Maltcev, V.: Context-free rewriting systems and word-hyperbolic structures with uniqueness. Int. J. Algebra Comput. 22(7) (2012). https://doi.org/10.1142/S0218196712500610
Campbell, C.M., Robertson, E.F., Ruškuc, N., Thomas, R.M.: Automatic semigroups. Theor. Comput. Sci. 250(1–2), 365–391 (2001). https://doi.org/10.1016/S0304-3975(99)00151-6
Duncan, A., Gilman, R.H.: Word hyperbolic semigroups. Math. Proc. Camb. Philos. Soc. 136(3), 513–524 (1999). https://doi.org/10.1017/S0305004103007497
Dunwoody, M.J.: The accessibility of finitely presented groups. Invent. Math. 81(3), 449–457 (1985). https://doi.org/10.1007/BF01388581
Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones & Bartlett, Boston (1992)
Gilman, R.H.: On the definition of word hyperbolic groups. Math. Z. 242(3), 529–541 (2002). https://doi.org/10.1007/s002090100356
Ginsburg, S., Greibach, S.: Deterministic context free languages. Inf. Control 9(6), 620–648 (1966). https://doi.org/10.1016/S0019-9958(66)80019-0
Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75–263. Springer, New York (1987). https://doi.org/10.1007/978-1-4613-9586-7_3
Herbst, T., Thomas, R.M.: Group presentations, formal languages and characterizations of one-counter groups. Theor. Comput. Sci. 112(2), 187–213 (1993). https://doi.org/10.1016/0304-3975(93)90018-O
Hoffmann, M., Holt, D.F., Owens, M.D., Thomas, R.M.: Semigroups with a context-free word problem. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 97–108. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31653-1_10
Hoffmann, M., Kuske, D., Otto, F., Thomas, R.M.: Some relatives of automatic and hyperbolic groups. In: Gomes, G.M.S., Pin, J.É., Silva, P.V. (eds.) Semigroups, Algorithms, Automata and Languages, pp. 379–406. World Scientific, River Edge (2002). https://doi.org/10.1142/9789812776884_0016
Holt, D.F., Owens, M.D., Thomas, R.M.: Groups and semigroups with a one-counter word problem. J. Aust. Math. Soc. 85(02), 197 (2008). https://doi.org/10.1017/S1446788708000864
Holt, D.F., Rees, S., Röver, C.E., Thomas, R.M.: Groups with context-free co-word problem. J. London Math. Soc. 71(3), 643–657 (1999). https://doi.org/10.1112/S002461070500654X
Holt, D.F., Röver, C.E.: Groups with indexed co-word problem. Int. J. Algebra Comput. 16(5), 985–1014 (2006). https://doi.org/10.1142/S0218196706003359
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 1st edn. Addison-Wesley, Reading (1979)
Howie, J.M.: Fundamentals of Semigroup Theory. London Mathematical Society Monographs: New Series, vol. 12. Clarendon Press, Oxford University Press, New York (1995)
Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. Syst. Sci. 26(3), 295–310 (1983). https://doi.org/10.1016/0022-0000(83)90003-X
Robertson, E.F., Ruškuc, N., Wiegold, J.: Generators and relations of direct products of semigroups. Trans. Am. Math. Soc. 350(07), 2665–2686 (1998). https://doi.org/10.1090/S0002-9947-98-02074-1
Acknowledgements
The first author was supported by the FCT (Fundação para a Ciência e a Tecnologia/Portuguese Foundation for Science and Technology) fellowship SFRH/BPD/121469/2016 and by the FCT project UID/Multi/04621/2013.
The second author was supported by the ‘Investigador FCT’ fellowship IF/01622/2013/CP1161/CT0001.
For the first and second authors, this work was partially supported by FCT projects UID/MAT/00297/2019 (Centro de Matemática e Aplicações), PTDC/MHC-FIL/2583/2014 and PTDC/MAT-PUR/31174/2017.
This work was started during a visit by the third author to the Universidade Nova de Lisboa, which was supported by the exploratory project IF/01622/2013/CP1161/CT0001 attached to the second author’s research fellowship.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Brough, T., Cain, A.J., Pfeiffer, M. (2019). Context-Free Word Problem Semigroups. In: Hofman, P., Skrzypczak, M. (eds) Developments in Language Theory. DLT 2019. Lecture Notes in Computer Science(), vol 11647. Springer, Cham. https://doi.org/10.1007/978-3-030-24886-4_22
Download citation
DOI: https://doi.org/10.1007/978-3-030-24886-4_22
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-24885-7
Online ISBN: 978-3-030-24886-4
eBook Packages: Computer ScienceComputer Science (R0)