{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T01:25:03Z","timestamp":1652664303325},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> Let G be a finitely generated virtually-free group. We consider the Birget\u2013Rhodes expansion of G, which yields an inverse monoid and which is denoted by IM (G) in the following. We show that for a finite idempotent presentation P, the word problem of a quotient monoid IM (G)\/P can be solved in linear time on a RAM. The uniform word problem, where G and the presentation P are also part of the input, is EXPTIME-complete. With IM (G)\/P we associate a relational structure, which contains for every rational subset L of IM (G)\/P a binary relation, consisting of all pairs (x,y) such that y can be obtained from x by right multiplication with an element from L. We prove that the first-order theory of this structure is decidable. This result implies that the emptiness problem for Boolean combinations of rational subsets of IM (G)\/P is decidable, which, in turn implies the decidability of the submonoid membership problem of IM (G)\/P. These results were known previously for free groups, only. Moreover, we provide a new algorithmic approach for these problems, which seems to be of independent interest even for free groups. <\/jats:p><jats:p> We also show that one cannot expect decidability results in much larger frameworks than virtually-free groups because the subgroup membership problem of a subgroup H in an arbitrary group G can be reduced to a word problem of some IM (G)\/P, where P depends only on H. A consequence is that there is a hyperbolic group G and a finite idempotent presentation P such that the word problem is undecidable for some finitely generated submonoid of IM (G)\/P. In particular, the word problem of IM (G)\/P is undecidable. <\/jats:p>","DOI":"10.1142\/s0218196708004366","type":"journal-article","created":{"date-parts":[[2008,2,22]],"date-time":"2008-02-22T10:57:59Z","timestamp":1203677879000},"page":"181-208","source":"Crossref","is-referenced-by-count":2,"title":["ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS"],"prefix":"10.1142","volume":"18","author":[{"given":"VOLKER","family":"DIEKERT","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Formale Methoden der Informatik (FMI), Universit\u00e4t Stuttgart, Universit\u00e4tsstr. 38, D-70569 Stuttgart, Germany"}]},{"given":"NICOLE","family":"ONDRUSCH","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Formale Methoden der Informatik (FMI), Universit\u00e4t Stuttgart, Universit\u00e4tsstr. 38, D-70569 Stuttgart, Germany"}]},{"given":"MARKUS","family":"LOHREY","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Leipzig, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)00063-W"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(84)90092-6"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(89)90199-3"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00030-9"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707003755"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001657"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.06.002"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.01.002"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90052-2"},{"key":"rf14","first-page":"259","volume":"335","author":"Margolis S.","journal-title":"Trans. Amer. Math. Soc."},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-0149-3_6"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/53.1.79"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90003-X"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90087-8"},{"key":"rf20","first-page":"385","volume":"30","author":"Munn W.","journal-title":"Proc. London Math. Soc."},{"key":"rf21","volume-title":"Inverse Semigroups","author":"Petrich M.","year":"1984"},{"key":"rf22","first-page":"1","volume":"141","author":"Rabin M. O.","journal-title":"Trans. Amer. Math. Soc."},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/14.1.45"},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00969107"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050045"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196792000128"},{"key":"rf27","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1051\/ita\/1996300403491","volume":"30","author":"Silva P. V.","journal-title":"RAIRO \u2014 Informatique Th\u00e9orique et Applications"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-4049(89)90054-6"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609302001406"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196708004366","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T22:28:45Z","timestamp":1565130525000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196708004366"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":26,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0218196708004366"],"URL":"https:\/\/doi.org\/10.1142\/s0218196708004366","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}