{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:24:57Z","timestamp":1725600297366},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229923"},{"type":"electronic","value":"9783642229930"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22993-0_41","type":"book-chapter","created":{"date-parts":[[2011,8,9]],"date-time":"2011-08-09T12:44:46Z","timestamp":1312893886000},"page":"448-459","source":"Crossref","is-referenced-by-count":1,"title":["Compressed Word Problems for Inverse Monoids"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"41_CR1","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P. Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J.\u00a0Comput.\u00a0Syst.\u00a0Sci.\u00a065(2), 332\u2013350 (2002)","journal-title":"J.\u00a0Comput.\u00a0Syst.\u00a0Sci."},{"issue":"2","key":"41_CR2","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/s00233-008-9060-x","volume":"77","author":"V. Diekert","year":"2008","unstructured":"Diekert, V., Lohrey, M., Miller, A.: Partially commutative inverse monoids. Semigroup Forum\u00a077(2), 196\u2013226 (2008)","journal-title":"Semigroup Forum"},{"key":"41_CR3","volume-title":"Inverse Semigroups: The Theory of Partial Symmetries","author":"M.V. Lawson","year":"1999","unstructured":"Lawson, M.V.: Inverse Semigroups: The Theory of Partial Symmetries. World Scientific, Singapore (1999)"},{"key":"41_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: A tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol.\u00a04580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"issue":"3","key":"41_CR5","first-page":"522","volume":"24","author":"R.J. Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J.\u00a0Assoc.\u00a0Comput.\u00a0Mach.\u00a024(3), 522\u2013526 (1977)","journal-title":"J.\u00a0Assoc.\u00a0Comput.\u00a0Mach."},{"key":"41_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-45127-7_16","volume-title":"Rewriting Techniques and Applications","author":"M. Lohrey","year":"2001","unstructured":"Lohrey, M.: On the parallel complexity of tree automata. In: Middeldorp, A. (ed.) RTA 2001. LNCS, vol.\u00a02051, pp. 201\u2013215. Springer, Heidelberg (2001)"},{"issue":"5","key":"41_CR7","doi-asserted-by":"publisher","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J.\u00a0Comput.\u00a035(5), 1210\u20131240 (2006)","journal-title":"SIAM J.\u00a0Comput."},{"issue":"6","key":"41_CR8","doi-asserted-by":"publisher","first-page":"951","DOI":"10.1016\/j.ic.2011.01.009","volume":"209","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M.: Leaf languages and string compression. Inf.\u00a0Comput.\u00a0209(6), 951\u2013965 (2011)","journal-title":"Inf.\u00a0Comput."},{"key":"41_CR9","unstructured":"Lohrey, M.: Compressed word problems for inverse monoids., \n                    \n                      http:\/\/arxiv.org\/abs\/1106.1000"},{"issue":"8","key":"41_CR10","doi-asserted-by":"publisher","first-page":"1212","DOI":"10.1016\/j.ic.2007.01.002","volume":"205","author":"M. Lohrey","year":"2007","unstructured":"Lohrey, M., Ondrusch, N.: Inverse monoids: decidability and complexity of algebraic questions. Inf. Comput.\u00a0205(8), 1212\u20131234 (2007)","journal-title":"Inf. Comput."},{"key":"41_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-540-74510-5_26","volume-title":"Computer Science \u2013 Theory and Applications","author":"M. Lohrey","year":"2007","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol.\u00a04649, pp. 249\u2013258. Springer, Heidelberg (2007)"},{"issue":"2","key":"41_CR12","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s00224-010-9264-9","volume":"48","author":"M. Lohrey","year":"2011","unstructured":"Lohrey, M., Steinberg, B.: Tilings and submonoids of metabelian groups. Theory Comput.\u00a0Syst.\u00a048(2), 411\u2013427 (2011)","journal-title":"Theory Comput.\u00a0Syst."},{"issue":"3","key":"41_CR13","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1142\/S021819671000542X","volume":"20","author":"J. Macdonald","year":"2010","unstructured":"Macdonald, J.: Compressed words and automorphisms in fully residually free groups. Internat.\u00a0J.\u00a0Algebra Comput.\u00a020(3), 343\u2013355 (2010)","journal-title":"Internat.\u00a0J.\u00a0Algebra Comput."},{"issue":"1","key":"41_CR14","doi-asserted-by":"publisher","first-page":"259","DOI":"10.2307\/2154268","volume":"335","author":"S. Margolis","year":"1993","unstructured":"Margolis, S., Meakin, J.: Inverse monoids, trees, and context-free languages. Trans. Amer. Math. Soc.\u00a0335(1), 259\u2013276 (1993)","journal-title":"Trans. Amer. Math. Soc."},{"key":"41_CR15","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/978-94-011-0149-3_6","volume-title":"Semigroups, Formal Languages and Groups","author":"S. Margolis","year":"1995","unstructured":"Margolis, S., Meakin, J., Sapir, M.: Algorithmic problems in groups, semigroups and inverse semigroups. In: Fountain, J. (ed.) Semigroups, Formal Languages and Groups, pp. 147\u2013214. Kluwer Academic Publishers, Dordrecht (1995)"},{"key":"41_CR16","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1112\/plms\/s3-29.3.385","volume":"30","author":"W. Munn","year":"1974","unstructured":"Munn, W.: Free inverse semigroups. Proc.London Math. Soc.\u00a030, 385\u2013404 (1974)","journal-title":"Proc.London Math. Soc."},{"key":"41_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"41_CR18","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 262\u2013272. Springer, Heidelberg (1999)"},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"860","DOI":"10.1007\/BF00969107","volume":"26","author":"B.V. Rozenblat","year":"1985","unstructured":"Rozenblat, B.V.: Diophantine theories of free inverse semigroups. Sib. Math. J.\u00a026, 860\u2013865 (1985); English translation","journal-title":"Sib. Math. J."},{"key":"41_CR20","doi-asserted-by":"publisher","first-page":"741","DOI":"10.4171\/CMH\/142","volume":"83","author":"S. Schleimer","year":"2008","unstructured":"Schleimer, S.: Polynomial-time word problems. Comment.\u00a0Math.\u00a0Helv.\u00a083, 741\u2013765 (2008)","journal-title":"Comment.\u00a0Math.\u00a0Helv."},{"key":"41_CR21","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218196792000128","volume":"2","author":"P.V. Silva","year":"1992","unstructured":"Silva, P.V.: Rational languages and inverse monoid presentations. Internat.\u00a0J.\u00a0Algebra Comput.\u00a02, 187\u2013207 (1992)","journal-title":"Internat.\u00a0J.\u00a0Algebra Comput."},{"key":"41_CR22","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0022-4049(90)90057-O","volume":"63","author":"J. Stephen","year":"1990","unstructured":"Stephen, J.: Presentations of inverse monoids. J.\u00a0Pure Appl.\u00a0Algebra\u00a063, 81\u2013112 (1990)","journal-title":"J.\u00a0Pure Appl.\u00a0Algebra"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22993-0_41.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T11:40:27Z","timestamp":1620042027000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22993-0_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229923","9783642229930"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22993-0_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}