{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T11:16:18Z","timestamp":1758280578158},"reference-count":76,"publisher":"Walter de Gruyter GmbH","issue":"2","funder":[{"name":"National Science Foundation","award":["DMS-1440140"],"award-info":[{"award-number":["DMS-1440140"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Suppose that <jats:italic>G<\/jats:italic> is a finitely generated group and <jats:inline-formula id=\"j_gcc-2018-0010_ineq_9999_w2aab2b8e1351b1b7b1aab1c14b1b3Aa\"><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_gcc-2018-0010_eq_0149.png\" \/><jats:tex-math>{\\operatorname{WP}(G)}<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the formal language of words defining the identity in <jats:italic>G<\/jats:italic>.\nWe prove that if <jats:italic>G<\/jats:italic> is a virtually nilpotent group that is not virtually abelian, the fundamental group of a finite volume hyperbolic three-manifold, or a right-angled Artin group whose graph lies in a certain infinite class, then <jats:inline-formula id=\"j_gcc-2018-0010_ineq_9998_w2aab2b8e1351b1b7b1aab1c14b1b9Aa\"><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_gcc-2018-0010_eq_0149.png\" \/><jats:tex-math>{\\operatorname{WP}(G)}<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is not a multiple context-free language.<\/jats:p>","DOI":"10.1515\/gcc-2018-0010","type":"journal-article","created":{"date-parts":[[2018,10,30]],"date-time":"2018-10-30T09:23:00Z","timestamp":1540891380000},"page":"53-62","source":"Crossref","is-referenced-by-count":6,"title":["Groups whose word problems are not semilinear"],"prefix":"10.1515","volume":"10","author":[{"given":"Robert H.","family":"Gilman","sequence":"first","affiliation":[{"name":"Department of Mathematics, Stevens Institute of Technology, HobokenNJ 07030, USA"}]},{"given":"Robert P.","family":"Kropholler","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Tufts University, MedfordMA 02135, USA"}]},{"given":"Saul","family":"Schleimer","sequence":"additional","affiliation":[{"name":"Mathematics Institute, University of Warwick, Coventry, United Kingdom"}]}],"member":"374","reference":[{"key":"ref581","volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979"},{"key":"ref241","first-page":"1","article-title":"Formal languages: An introduction and a synopsis","year":"1997","journal-title":"Handbook of Formal Languages. Vol. 1"},{"key":"ref111","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/j.tcs.2005.03.026","article-title":"A context-free and a 1-counter geodesic language for a Baumslag\u2013Solitar group","volume":"339","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"ref511","volume-title":"Algebraic and Automata-theoretic Properties of Formal Languages","year":"1975"},{"key":"ref531","volume-title":"The Theory of Groups","year":"1959"},{"key":"ref521","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1007\/s00039-007-0629-4","article-title":"Special cube complexes","volume":"17","year":"2008","journal-title":"Geom. Funct. Anal."},{"key":"ref431","volume-title":"Graph Classes: A Survey","year":"1999"},{"key":"ref671","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1017\/S0004972715000015","article-title":"On groups presented by monadic rewriting systems with generators of finite order","volume":"91","year":"2015","journal-title":"Bull. Aust. Math. Soc."},{"key":"ref711","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1090\/S0273-0979-1982-15003-0","article-title":"Three-dimensional manifolds, Kleinian groups and hyperbolic geometry","volume":"6","year":"1982","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"ref251","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","article-title":"Groups, the theory of ends, and context-free languages","volume":"26","year":"1983","journal-title":"J. Comput. System Sci."},{"key":"ref21","volume-title":"3-manifold Groups","year":"2015"},{"key":"ref261","doi-asserted-by":"crossref","first-page":"339","DOI":"10.5802\/aif.287","article-title":"Transductions des langages de Chomsky","volume":"18","year":"1968","journal-title":"Ann. Inst. Fourier (Grenoble)"},{"key":"ref441","first-page":"9","article-title":"Groups with poly-context-free word problem","volume":"6","year":"2014","journal-title":"Groups Complex. Cryptol."},{"key":"ref551","first-page":"9","article-title":"The word problem of \u2124n\\mathbb{Z}^{n} is a multiple context-free language","volume":"10","year":"2018","journal-title":"Groups Complex. Cryptol."},{"key":"ref751","article-title":"The structure of groups with a quasiconvex hierarchy","year":"2011","journal-title":"Preprint"},{"key":"ref371","article-title":"The structure of groups with a quasiconvex hierarchy","year":"2011","journal-title":"Preprint"},{"key":"ref291","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1017\/S0004972715000015","article-title":"On groups presented by monadic rewriting systems with generators of finite order","volume":"91","year":"2015","journal-title":"Bull. Aust. Math. Soc."},{"key":"ref721","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1090\/S0273-0979-1988-15685-6","article-title":"On the geometry and dynamics of diffeomorphisms of surfaces","volume":"19","year":"1988","journal-title":"Bull. Amer. Math. Soc. (N.\u2009S.)"},{"key":"ref231","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1112\/blms\/bdl043","article-title":"The co-word problem for the Higman\u2013Thompson group is context-free","volume":"39","year":"2007","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref691","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","article-title":"On multiple context-free grammars","volume":"88","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"ref331","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1090\/S0273-0979-1982-15003-0","article-title":"Three-dimensional manifolds, Kleinian groups and hyperbolic geometry","volume":"6","year":"1982","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"ref191","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0218196711006133","article-title":"Groups with context-free conjugacy problems","volume":"21","year":"2011","journal-title":"Internat. J. Algebra Comput."},{"key":"ref351","first-page":"104","article-title":"Characterizing structural descriptions produced by various grammatical formalisms","year":"1987","journal-title":"Proceedings of the 25th Annual Meeting on Association for Computational Linguistics\u2014ACL \u201987"},{"key":"ref81","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","article-title":"\u00dcber unendliche diskontinuierliche Gruppen","volume":"71","year":"1911","journal-title":"Math. Ann."},{"key":"ref61","first-page":"9","article-title":"Groups with poly-context-free word problem","volume":"6","year":"2014","journal-title":"Groups Complex. Cryptol."},{"key":"ref151","volume-title":"The Theory of Groups","year":"1959"},{"key":"ref01","first-page":"1045","article-title":"The virtual Haken conjecture","volume":"18","year":"2013","journal-title":"Doc. Math."},{"key":"ref701","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0021-8693(89)90319-0","article-title":"Automorphisms of graph groups","volume":"126","year":"1989","journal-title":"J. Algebra"},{"key":"ref321","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/0021-8693(89)90319-0","article-title":"Automorphisms of graph groups","volume":"126","year":"1989","journal-title":"J. Algebra"},{"key":"ref301","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1016\/j.jcss.2015.03.004","article-title":"MIX is a 2-MCFL and the word problem in \u21242\\mathbb{Z}^{2} is captured by the IO and the OI hierarchies","volume":"81","year":"2015","journal-title":"J. Comput. System Sci."},{"key":"ref221","article-title":"The class of groups with MCF word problem is closed under free products","year":"2017","journal-title":"Preprint"},{"key":"ref681","doi-asserted-by":"crossref","first-page":"1252","DOI":"10.1016\/j.jcss.2015.03.004","article-title":"MIX is a 2-MCFL and the word problem in \u21242\\mathbb{Z}^{2} is captured by the IO and the OI hierarchies","volume":"81","year":"2015","journal-title":"J. Comput. System Sci."},{"key":"ref171","first-page":"9","article-title":"The word problem of \u2124n\\mathbb{Z}^{n} is a multiple context-free language","volume":"10","year":"2018","journal-title":"Groups Complex. Cryptol."},{"key":"ref731","first-page":"104","article-title":"Characterizing structural descriptions produced by various grammatical formalisms","year":"1987","journal-title":"Proceedings of the 25th Annual Meeting on Association for Computational Linguistics\u2014ACL \u201987"},{"key":"ref91","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1090\/S0002-9939-99-04873-X","article-title":"Presentations for subgroups of Artin groups","volume":"127","year":"1999","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref391","first-page":"18","article-title":"The group languages","volume":"4","year":"1971","journal-title":"Kibernet. (Kiev)"},{"key":"ref201","volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979"},{"key":"ref481","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1142\/S0218196713500124","article-title":"Context-free groups and their structure trees","volume":"23","year":"2013","journal-title":"Internat. J. Algebra Comput."},{"key":"ref31","volume-title":"Lecture Notes on Nilpotent Groups","year":"1971"},{"key":"ref11","first-page":"18","article-title":"The group languages","volume":"4","year":"1971","journal-title":"Kibernet. (Kiev)"},{"key":"ref541","volume-title":"Introduction to Formal Language Theory","year":"1978"},{"key":"ref51","volume-title":"Graph Classes: A Survey","year":"1999"},{"key":"ref591","volume-title":"Parsing Beyond Context-free Grammars","year":"2010"},{"key":"ref631","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1016\/0022-0000(83)90003-X","article-title":"Groups, the theory of ends, and context-free languages","volume":"26","year":"1983","journal-title":"J. Comput. System Sci."},{"key":"ref101","doi-asserted-by":"crossref","first-page":"611","DOI":"10.1142\/S0218196713500124","article-title":"Context-free groups and their structure trees","volume":"23","year":"2013","journal-title":"Internat. J. Algebra Comput."},{"key":"ref461","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/BF01456932","article-title":"\u00dcber unendliche diskontinuierliche Gruppen","volume":"71","year":"1911","journal-title":"Math. Ann."},{"key":"ref71","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.tcs.2015.06.054","article-title":"Multipass automata and group word problems","volume":"600","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"ref311","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","article-title":"On multiple context-free grammars","volume":"88","year":"1991","journal-title":"Theoret. Comput. Sci."},{"key":"ref741","first-page":"44","article-title":"Research announcement: the structure of groups with a quasiconvex hierarchy","volume":"16","year":"2009","journal-title":"Electron. Res. Announc. Math. Sci."},{"key":"ref571","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1142\/S0218196711006133","article-title":"Groups with context-free conjugacy problems","volume":"21","year":"2011","journal-title":"Internat. J. Algebra Comput."},{"key":"ref161","volume-title":"Introduction to Formal Language Theory","year":"1978"},{"key":"ref381","first-page":"1045","article-title":"The virtual Haken conjecture","volume":"18","year":"2013","journal-title":"Doc. Math."},{"key":"ref141","doi-asserted-by":"crossref","first-page":"1551","DOI":"10.1007\/s00039-007-0629-4","article-title":"Special cube complexes","volume":"17","year":"2008","journal-title":"Geom. Funct. Anal."},{"key":"ref471","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1090\/S0002-9939-99-04873-X","article-title":"Presentations for subgroups of Artin groups","volume":"127","year":"1999","journal-title":"Proc. Amer. Math. Soc."},{"key":"ref181","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1017\/S1446788708000864","article-title":"Groups and semigroups with a one-counter word problem","volume":"85","year":"2008","journal-title":"J. Aust. Math. Soc."},{"key":"ref451","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.tcs.2015.06.054","article-title":"Multipass automata and group word problems","volume":"600","year":"2015","journal-title":"Theoret. Comput. Sci."},{"key":"ref411","volume-title":"Lecture Notes on Nilpotent Groups","year":"1971"},{"key":"ref611","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1112\/blms\/bdl043","article-title":"The co-word problem for the Higman\u2013Thompson group is context-free","volume":"39","year":"2007","journal-title":"Bull. Lond. Math. Soc."},{"key":"ref341","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1090\/S0273-0979-1988-15685-6","article-title":"On the geometry and dynamics of diffeomorphisms of surfaces","volume":"19","year":"1988","journal-title":"Bull. Amer. Math. Soc. (N.\u2009S.)"},{"key":"ref501","first-page":"27","article-title":"Formal languages and infinite groups","year":"1996","journal-title":"Geometric and Computational Perspectives on Infinite Groups"},{"key":"ref421","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1090\/S0002-9904-1962-10745-9","article-title":"Some two-generator one-relator non-Hopfian groups","volume":"68","year":"1962","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref401","volume-title":"3-manifold Groups","year":"2015"},{"key":"ref641","doi-asserted-by":"crossref","first-page":"339","DOI":"10.5802\/aif.287","article-title":"Transductions des langages de Chomsky","volume":"18","year":"1968","journal-title":"Ann. Inst. Fourier (Grenoble)"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1090\/S0002-9904-1962-10745-9","article-title":"Some two-generator one-relator non-Hopfian groups","volume":"68","year":"1962","journal-title":"Bull. Amer. Math. Soc."},{"key":"ref131","volume-title":"Algebraic and Automata-theoretic Properties of Formal Languages","year":"1975"},{"key":"ref281","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1081\/AGB-120004481","article-title":"Groups with context-free reduced word problem","volume":"30","year":"2002","journal-title":"Comm. Algebra"},{"key":"ref271","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0218196701000401","article-title":"Length and area functions on groups and quasi-isometric Higman embeddings","volume":"11","year":"2001","journal-title":"Internat. J. Algebra Comput."},{"key":"ref661","doi-asserted-by":"crossref","first-page":"3143","DOI":"10.1081\/AGB-120004481","article-title":"Groups with context-free reduced word problem","volume":"30","year":"2002","journal-title":"Comm. Algebra"},{"key":"ref361","first-page":"44","article-title":"Research announcement: the structure of groups with a quasiconvex hierarchy","volume":"16","year":"2009","journal-title":"Electron. Res. Announc. Math. Sci."},{"key":"ref621","first-page":"1","article-title":"Formal languages: An introduction and a synopsis","year":"1997","journal-title":"Handbook of Formal Languages. Vol. 1"},{"key":"ref491","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/j.tcs.2005.03.026","article-title":"A context-free and a 1-counter geodesic language for a Baumslag\u2013Solitar group","volume":"339","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"ref561","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1017\/S1446788708000864","article-title":"Groups and semigroups with a one-counter word problem","volume":"85","year":"2008","journal-title":"J. Aust. Math. Soc."},{"key":"ref601","article-title":"The class of groups with MCF word problem is closed under free products","year":"2017","journal-title":"Preprint"},{"key":"ref121","first-page":"27","article-title":"Formal languages and infinite groups","year":"1996","journal-title":"Geometric and Computational Perspectives on Infinite Groups"},{"key":"ref211","volume-title":"Parsing Beyond Context-free Grammars","year":"2010"},{"key":"ref651","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1142\/S0218196701000401","article-title":"Length and area functions on groups and quasi-isometric Higman embeddings","volume":"11","year":"2001","journal-title":"Internat. J. Algebra Comput."}],"container-title":["Groups Complexity Cryptology"],"original-title":[],"link":[{"URL":"https:\/\/www.degruyter.com\/view\/journals\/gcc\/10\/2\/article-p53.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/downloadpdf\/journals\/gcc\/10\/2\/article-p53.xml","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T03:08:52Z","timestamp":1614395332000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/gcc-2018-0010\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,1]]},"references-count":76,"journal-issue":{"issue":"2"},"URL":"https:\/\/doi.org\/10.1515\/gcc-2018-0010","relation":{},"ISSN":["1867-1144","1869-6104"],"issn-type":[{"value":"1867-1144","type":"print"},{"value":"1869-6104","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,1]]}}}