{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T07:50:07Z","timestamp":1742975407596,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031055775"},{"type":"electronic","value":"9783031055782"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-05578-2_21","type":"book-chapter","created":{"date-parts":[[2022,5,8]],"date-time":"2022-05-08T17:06:22Z","timestamp":1652029582000},"page":"263-273","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Rational Index of\u00a0Languages with\u00a0Bounded Dimension of\u00a0Parse Trees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1577-8347","authenticated-orcid":false,"given":"Ekaterina","family":"Shemetova","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7966-0698","authenticated-orcid":false,"given":"Semyon","family":"Grigorev","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,6]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","unstructured":"Afrati, F., Papadimitriou, C.: The parallel complexity of simple chain queries. In: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1987, pp. 210\u2013213. ACM, New York (1987). https:\/\/doi.org\/10.1145\/28659.28682","DOI":"10.1145\/28659.28682"},{"issue":"1\u20134","key":"21_CR2","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1524\/stuf.1961.14.14.143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phreise structure grammars. STUF Lang. Typol. Univ. 14(1\u20134), 143\u2013172 (1961). https:\/\/doi.org\/10.1524\/stuf.1961.14.14.143","journal-title":"STUF Lang. Typol. Univ."},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1137\/0210020","volume":"10","author":"L Boasson","year":"1981","unstructured":"Boasson, L., Courcelle, B., Nivat, M.: The rational index: a complexity measure for languages. SIAM J. Comput. 10(2), 284\u2013296 (1981)","journal-title":"SIAM J. Comput."},{"key":"21_CR4","doi-asserted-by":"publisher","unstructured":"Brzozowski, J.A.: Regular-like expressions for some irregular languages. In: 9th Annual Symposium on Switching and Automata Theory (swat 1968), pp. 278\u2013286 (1968). https:\/\/doi.org\/10.1109\/SWAT.1968.24","DOI":"10.1109\/SWAT.1968.24"},{"key":"21_CR5","doi-asserted-by":"publisher","unstructured":"Chistikov, D., Czerwinski, W., Hofman, P., Pilipczuk, M., Wehar, M.: Shortest paths in one-counter systems. Log. Methods Comput. Sci. 15(1) (2019). https:\/\/doi.org\/10.23638\/LMCS-15(1:19)2019","DOI":"10.23638\/LMCS-15(1:19)2019"},{"key":"21_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/3-540-52282-4_33","volume-title":"STACS 90","author":"MP Chytil","year":"1990","unstructured":"Chytil, M.P., Monien, B.: Caterpillars and context-free languages. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol. 415, pp. 70\u201381. Springer, Heidelberg (1990). https:\/\/doi.org\/10.1007\/3-540-52282-4_33"},{"key":"21_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-319-04921-2_1","volume-title":"Language and Automata Theory and Applications","author":"J Esparza","year":"2014","unstructured":"Esparza, J., Luttenberger, M., Schlund, M.: A brief history of strahler numbers. In: Dediu, A.-H., Mart\u00edn-Vide, C., Sierra-Rodr\u00edguez, J.-L., Truthe, B. (eds.) LATA 2014. LNCS, vol. 8370, pp. 1\u201313. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-04921-2_1"},{"key":"21_CR8","doi-asserted-by":"publisher","first-page":"178","DOI":"10.4204\/eptcs.226.13","volume":"226","author":"P Ganty","year":"2016","unstructured":"Ganty, P., Valput, D.: Bounded-oscillation pushdown automata. Electron. Proc. Theor. Comput. Sci. 226, 178\u2013197 (2016). https:\/\/doi.org\/10.4204\/eptcs.226.13","journal-title":"Electron. Proc. Theor. Comput. Sci."},{"key":"21_CR9","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-completeness Theory","author":"R Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-completeness Theory. Oxford University Press Inc., New York (1995)"},{"key":"21_CR10","unstructured":"Hellings, J.: Path results for context-free grammar queries on graphs. CoRR abs\/1502.02242 (2015)"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-22321-1_24","volume-title":"Developments in Language Theory","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M., Leiter, U.: Nodes connected by path languages. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 276\u2013287. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22321-1_24"},{"key":"21_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-319-09704-6_23","volume-title":"Descriptional Complexity of Formal Systems","author":"B Komarath","year":"2014","unstructured":"Komarath, B., Sarma, J., Sunil, K.S.: On the complexity of L-reachability. In: J\u00fcrgensen, H., Karhum\u00e4ki, J., Okhotin, A. (eds.) DCFS 2014. LNCS, vol. 8614, pp. 258\u2013269. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-09704-6_23"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.ic.2015.11.008","volume":"246","author":"M Luttenberger","year":"2016","unstructured":"Luttenberger, M., Schlund, M.: Convergence of newton\u2019s method over commutative semirings. Inf. Comput. 246, 43\u201361 (2016). https:\/\/doi.org\/10.1016\/j.ic.2015.11.008","journal-title":"Inf. Comput."},{"issue":"2","key":"21_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(92)90269-L","volume":"95","author":"L Pierre","year":"1992","unstructured":"Pierre, L.: Rational indexes of generators of the cone of context-free languages. Theor. Comput. Sci. 95(2), 279\u2013305 (1992). https:\/\/doi.org\/10.1016\/0304-3975(92)90269-L","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1051\/ita\/1990240302751","volume":"24","author":"L Pierre","year":"1990","unstructured":"Pierre, L., Farinone, J.M.: Context-free languages with rational index in $$\\theta (n^\\gamma )$$ for algebraic numbers $$\\gamma $$. RAIRO - Theor. Inf. Appl. - Informatique Th\u00e9orique et Appl. 24(3), 275\u2013322 (1990)","journal-title":"RAIRO - Theor. Inf. Appl. - Informatique Th\u00e9orique et Appl."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1016\/S0950-5849(98)00093-7","volume":"40","author":"TW Reps","year":"1997","unstructured":"Reps, T.W.: Program analysis via graph reachability. Inf. Softw. Technol. 40, 701\u2013726 (1997)","journal-title":"Inf. Softw. Technol."},{"key":"21_CR17","doi-asserted-by":"publisher","unstructured":"Ullman, J.D., Van Gelder, A.: Parallel complexity of logical query programs. In: 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), pp. 438\u2013454 (Oct 1986). https:\/\/doi.org\/10.1109\/SFCS.1986.40","DOI":"10.1109\/SFCS.1986.40"},{"key":"21_CR18","unstructured":"Wechsung, G.: The oscillation complexity and a hierarchy of context-free languages. In: Fundamentals of Computation Theory, FCT 1979, Proceedings of the Conference on Algebraic, Arthmetic, and Categorial Methods in Computation Theory, Berlin\/Wendisch-Rietz, Germany, 17\u201321 September 1979, pp. 508\u2013515 (1979)"},{"key":"21_CR19","doi-asserted-by":"publisher","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Rosenkrantz, D.J., Sagiv, Y. (eds.) Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Nashville, Tennessee, USA, April 2\u20134, 1990, pp. 230\u2013242. ACM Press (1990). https:\/\/doi.org\/10.1145\/298514.298576","DOI":"10.1145\/298514.298576"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-05578-2_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,8]],"date-time":"2022-05-08T17:07:47Z","timestamp":1652029667000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-05578-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031055775","9783031055782"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-05578-2_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"6 May 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tampa, FL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 May 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 May 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.usf.edu\/arts-sciences\/conferences\/dlt2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"66% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}