{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T16:30:11Z","timestamp":1775061011010,"version":"3.50.1"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032224682","type":"print"},{"value":"9783032224699","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22469-9_13","type":"book-chapter","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:57:32Z","timestamp":1775055452000},"page":"229-247","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Reachability Problem on\u00a0Monoid-Labelled Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Nagashri","family":"Krishnakumar","sequence":"first","affiliation":[]},{"given":"Harshil","family":"Mittal","sequence":"additional","affiliation":[]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,2]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Allender, E.: Reachability Problems: An Update. In: Cooper, S.B., L\u00f6we, B., Sorbi, A. (eds) Computation and Logic in the Real World, Third Conference on Computability in Europe, CiE 2007, Siena, Italy, June 18\u201323, 2007, Proceedings. Lecture Notes in Computer Science, vol.\u00a04497, pp. 25\u201327. Springer, Cham (2007). https:\/\/doi.org\/10.1007\/978-3-540-73001-9_3","DOI":"10.1007\/978-3-540-73001-9_3"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Barrington, D.A.: Bounded-width polynomial-size branching programs recognize exactly those languages in $${\\sf NC}^1$$. In: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing (STOC 1986), pp.\u00a01\u20135 (1986)","DOI":"10.1145\/12130.12131"},{"issue":"4","key":"13_CR3","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"DAM Barrington","year":"1988","unstructured":"Barrington, D.A.M., Therien, D.: Finite monoids and the fine structure of $${ NC}^1$$. J. ACM (JACM) 35(4), 941\u2013952 (1988)","journal-title":"J. ACM (JACM)"},{"issue":"10","key":"13_CR4","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1073\/pnas.44.10.1061","volume":"44","author":"WW Boone","year":"1958","unstructured":"Boone, W.W.: The word problem. Proc. Natl. Acad. Sci. 44(10), 1061\u20131065 (1958)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Chandra, A.K., Fortune, S., Lipton, R.: Unbounded fan-in circuits and associative functions. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 52\u201360 (1983)","DOI":"10.1145\/800061.808732"},{"key":"13_CR6","doi-asserted-by":"publisher","unstructured":"Colcombet, T.: Green\u2019s Relations and Their Use in Automata Theory. In: Dediu, AH., Inenaga, S., Mart\u00edn-Vide, C. (eds.) Language and Automata Theory and Applications (LATA 2011), Lecture Notes in Computer Science, vol.\u00a06638, pp. 1\u201321. Springer, Cham (2011). https:\/\/doi.org\/10.1007\/978-3-642-21254-3_1","DOI":"10.1007\/978-3-642-21254-3_1"},{"issue":"3","key":"13_CR7","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1007\/s00233-020-10099-1","volume":"101","author":"R Gigo\u0144","year":"2020","unstructured":"Gigo\u0144, R.: Some results on $$\\cal{L} $$-commutative semigroups. Semigroup Forum 101(3), 385\u2013399 (2020)","journal-title":"Semigroup Forum"},{"issue":"3","key":"13_CR8","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00224-005-1279-2","volume":"40","author":"O Kl\u00edma","year":"2007","unstructured":"Kl\u00edma, O., Tesson, P., Th\u00e9rien, D.: Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst. 40(3), 263\u2013297 (2007)","journal-title":"Theory Comput. Syst."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Komarath, B., Sarma, J., Sunil, K.S.: On the Complexity of L-reachability. In: Descriptional Complexity of Formal Systems (DCFS 2014), pp. 258\u2013269 (2014)","DOI":"10.1007\/978-3-319-09704-6_23"},{"issue":"1","key":"13_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.2140\/pjm.1984.111.125","volume":"111","author":"SW Margolis","year":"1984","unstructured":"Margolis, S.W., \u00c9ric Pin, J.: Minimal noncommutative varieties and power varieties. Pac. J. Math. 111(1), 125\u2013135 (1984)","journal-title":"Pac. J. Math."},{"issue":"3","key":"13_CR11","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s00233-013-9557-9","volume":"88","author":"X Mary","year":"2014","unstructured":"Mary, X.: Classes of semigroups modulo Green\u2019s relation $$\\cal{H} $$. Semigroup Forum 88(3), 647\u2013669 (2014)","journal-title":"Semigroup Forum"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Nagy, A.: Special Classes of Semigroups, vol.\u00a01. Springer Science & Business Media (2001)","DOI":"10.1007\/978-1-4757-3316-7_1"},{"issue":"9","key":"13_CR13","first-page":"1","volume":"2","author":"PS Novikov","year":"1958","unstructured":"Novikov, P.S.: Algorithmic unsolvability of the word problem in group theory. Am. Math. Soc. Translations Ser. 2(9), 1\u2013122 (1958)","journal-title":"Am. Math. Soc. Translations Ser."},{"key":"13_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-2215-3","volume-title":"Varieties of Formal Languages","author":"JE Pin","year":"1986","unstructured":"Pin, J.E.: Varieties of Formal Languages. North Oxford Academic Publishing Co Ltd, Foundations of Computer Science (1986)"},{"issue":"2","key":"13_CR15","first-page":"284","volume":"22","author":"N Pipattanajinda","year":"2016","unstructured":"Pipattanajinda, N., Knauer, U., Gyurov, B., Panma, S.: The Endomorphism Monoids of $$(n-3)$$-regular Graphs of Order $$n$$. Algebra Discrete Math. 22(2), 284\u2013300 (2016)","journal-title":"Algebra Discrete Math."},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jcss.2019.04.002","volume":"105","author":"V Ramaswamy","year":"2019","unstructured":"Ramaswamy, V., Sarma, J., Sunil, K.S.: Space complexity of reachability testing in labelled graphs. J. Comput. Syst. Sci. 105, 40\u201353 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"13_CR17","unstructured":"Reingold, O.: Undirected ST-Connectivity in Log-Space. Electron. Colloquium Comput. Complex. TR04(094) (2004)"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Reingold, O., Trevisan, L., Vadhan, S.: Pseudorandom walks on regular digraphs and the RL vs. L problem. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006), pp. 457\u2013466 (2006)","DOI":"10.1145\/1132516.1132583"},{"key":"13_CR19","unstructured":"Tesson, P.: An Algebraic Approach to Communication Complexity. Ph.D. thesis, McGill University, Montreal, Canada (1998)"}],"container-title":["Lecture Notes in Computer Science","Relational and Algebraic Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22469-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:57:33Z","timestamp":1775055453000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22469-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032224682","9783032224699"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22469-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RAMICS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Relational and Algebraic Methods in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"B\u0119dlewo","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ramics2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ramics-conf.github.io\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}