{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T11:40:07Z","timestamp":1749987607320,"version":"3.41.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319537320"},{"type":"electronic","value":"9783319537337"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-53733-7_26","type":"book-chapter","created":{"date-parts":[[2017,2,15]],"date-time":"2017-02-15T10:39:21Z","timestamp":1487155161000},"page":"351-363","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space Complexity of Reachability Testing in Labelled Graphs"],"prefix":"10.1007","author":[{"given":"Vidhya","family":"Ramaswamy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K. S.","family":"Sunil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,2,16]]},"reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/978-3-540-73001-9_3","volume-title":"Computation and Logic in the Real World","author":"E Allender","year":"2007","unstructured":"Allender, E.: Reachability problems: an update. In: Cooper, S.B., L\u00f6we, B., Sorbi, A. (eds.) CiE 2007. LNCS, vol. 4497, pp. 25\u201327. Springer, Heidelberg (2007). doi: 10.1007\/978-3-540-73001-9_3"},{"key":"26_CR2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"issue":"4","key":"26_CR3","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1145\/48014.63138","volume":"35","author":"A David","year":"1988","unstructured":"David, A., Barrington, M., Th\u00e9rien, D.: Finite monoids and the fine structure of NC $${}^{\\text{1 }}$$ . J. ACM 35(4), 941\u2013952 (1988)","journal-title":"J. ACM"},{"key":"26_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/3-540-63165-8_169","volume-title":"Automata, Languages and Programming","author":"M Beaudry","year":"1997","unstructured":"Beaudry, M., Lemieux, F., Th\u00e9rien, D.: Finite loops recognize exactly the regular open languages. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol. 1256, pp. 110\u2013120. Springer, Heidelberg (1997). doi: 10.1007\/3-540-63165-8_169"},{"issue":"1","key":"26_CR5","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1137\/S0097539793249530","volume":"26","author":"M Beaudry","year":"1997","unstructured":"Beaudry, M., McKenzie, P., Pladeau, P., Th\u00e9rien, D.: Finite monoids: from word to circuit evaluation. SIAM J. Comput. 26(1), 138\u2013152 (1997)","journal-title":"SIAM J. Comput."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"B\u00e9dard, F., Lemieux, F., McKenzie, P.: Extensions to Barrington\u2019s M-program model. In: Proceedings Fifth Annual Structure in Complexity Theory Conference, pp. 200\u2013209 (1990)","DOI":"10.1109\/SCT.1990.113968"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Bourke, C., Tewari, R., Vinodchandran, N.V.: Directed planar reachability is in unambiguous log-space. ACM Trans. Comput. Theory 1(1), 4 (2009)","DOI":"10.1145\/1490270.1490274"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/3-540-58715-2_112","volume-title":"Foundation of Software Technology and Theoretical Computer Science","author":"H Caussinus","year":"1994","unstructured":"Caussinus, H., Lemieux, F.: The complexity of computing over quasigroups. In: Thiagarajan, P.S. (ed.) FSTTCS 1994. LNCS, vol. 880, pp. 36\u201347. Springer, Heidelberg (1994). doi: 10.1007\/3-540-58715-2_112"},{"issue":"2","key":"26_CR9","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1016\/0022-0000(85)90015-7","volume":"30","author":"AK Chandra","year":"1985","unstructured":"Chandra, A.K., Fortune, S., Lipton, R.J.: Unbounded fan-in circuits and associative functions. J. Comput. Syst. Sci. 30(2), 222\u2013234 (1985)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR10","unstructured":"Das, B., Datta, S., Nimbhorkar, P.: Log-space algorithms for paths and matchings in k-trees. In: 27th STACS, pp. 215\u2013226 (2010)"},{"issue":"1","key":"26_CR11","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.jctb.2008.07.003","volume":"99","author":"J Geelen","year":"2009","unstructured":"Geelen, J., Gerards, B.: Excluding a group-labelled graph. J. Comb. Theory Ser. B 99(1), 247\u2013253 (2009)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"26_CR12","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/77606.77608","volume":"12","author":"S Horwitz","year":"1990","unstructured":"Horwitz, S., Reps, T.W., Binkley, D.: Interprocedural slicing using dependence graphs. ACM Trans. Program. Lang. Syst. 12(1), 26\u201360 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"26_CR13","unstructured":"Huynh, T.C.T.: The linkage problem for group-labelled graphs. Ph.D. thesis, University of Waterloo (2009)"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1007\/978-3-662-47672-7_65","volume-title":"Automata, Languages, and Programming","author":"Y Kawase","year":"2015","unstructured":"Kawase, Y., Kobayashi, Y., Yamaguchi, Y.: Finding a path in group-labeled graphs with two labels forbidden. In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 797\u2013809. Springer, Heidelberg (2015). doi: 10.1007\/978-3-662-47672-7_65"},{"issue":"4","key":"26_CR15","doi-asserted-by":"publisher","first-page":"471","DOI":"10.3233\/FI-2016-1371","volume":"145","author":"B Komarath","year":"2016","unstructured":"Komarath, B., Sarma, J., Sunil, K.S.: On the complexity of L-reachability. Fundam. Inform. 145(4), 471\u2013483 (2016)","journal-title":"Fundam. Inform."},{"issue":"3","key":"26_CR16","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0022-4049(88)90097-7","volume":"52","author":"J-E Pin","year":"1988","unstructured":"Pin, J.-E., Straubing, H., Therien, D.: Locally trivial categories and unambiguous concatenation. J. Pure Appl. Algebra 52(3), 297\u2013311 (1988)","journal-title":"J. Pure Appl. Algebra"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BFb0055038","volume-title":"Automata, Languages and Programming","author":"J-F\u00c7 Raymond","year":"1998","unstructured":"Raymond, J.-F.\u00c7., Tesson, P., Th\u00e9rien, D.: An algebraic approach to communication complexity. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 29\u201340. Springer, Heidelberg (1998). doi: 10.1007\/BFb0055038"},{"key":"26_CR18","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17 (2008)","DOI":"10.1145\/1391289.1391291"},{"key":"26_CR19","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 STOC, pp. 457\u2013466 (2006)","DOI":"10.1145\/1132516.1132583"},{"issue":"8","key":"26_CR20","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1007\/s002360050068","volume":"33","author":"TW Reps","year":"1996","unstructured":"Reps, T.W.: On the sequential nature of interprocedural program-analysis problems. Acta Inform. 33(8), 739\u2013757 (1996)","journal-title":"Acta Inform."},{"issue":"11\u201312","key":"26_CR21","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"TW Reps","year":"1998","unstructured":"Reps, T.W.: Program analysis via graph reachability. Inf. Softw. Technol. 40(11\u201312), 701\u2013726 (1998)","journal-title":"Inf. Softw. Technol."},{"key":"26_CR22","unstructured":"Tesson, P.: An algebraic approach to communication complexity. Masters thesis, McGill University, Montreal (1998)"},{"key":"26_CR23","doi-asserted-by":"crossref","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the 9th ACM PODS, pp. 230\u2013242 (1990)","DOI":"10.1145\/298514.298576"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-53733-7_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T11:17:08Z","timestamp":1749986228000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-53733-7_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319537320","9783319537337"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-53733-7_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"16 February 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Language and Automata Theory and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Ume\u00e5","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sweden","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 March 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"lata2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/grammars.grlmc.com\/LATA2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}