{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T17:53:15Z","timestamp":1769881995357,"version":"3.49.0"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031177149","type":"print"},{"value":"9783031177156","type":"electronic"}],"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-17715-6_27","type":"book-chapter","created":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T09:02:27Z","timestamp":1664701347000},"page":"425-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Formal Grammars for\u00a0Turn-Bounded Deterministic Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Tomoyuki","family":"Yamakami","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,3]]},"reference":[{"key":"27_CR1","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Handbook of Formal Languages","author":"J-M Autebert","year":"1997","unstructured":"Autebert, J.-M., Berstel, J., Boasson, L.: Context-Free Languages and Pushdown Automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 111\u2013174. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59136-5_3"},{"key":"27_CR2","doi-asserted-by":"publisher","unstructured":"Berstel, J.: Transductions and Context-Free Languages. Teubner Verlag, Wiesbaden (1979). https:\/\/doi.org\/10.1007\/978-3-663-09367-1","DOI":"10.1007\/978-3-663-09367-1"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/S0022-0000(73)80036-4","volume":"7","author":"L Boasson","year":"1973","unstructured":"Boasson, L.: Two iteration theorems for some families of languages. J. Comput. Syst. Sci. 7, 583\u2013596 (1973)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.: Reversal complexity of counter machines. In: Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing (STOC 1981), pp. 146\u2013157 (1981)","DOI":"10.1145\/800076.802468"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.jcss.2018.02.003","volume":"104","author":"J Eremondi","year":"2019","unstructured":"Eremondi, J., Ibarra, O.H., McQuillan, I.: Insertion operations on deterministic reversal-bounded counter machines. J. Comput. Syst. Sci. 104, 244\u2013257 (2019)","journal-title":"J. Comput. Syst. Sci."},{"key":"27_CR6","unstructured":"Fernau, H., Wolf, P., Yamakami, T.: Synchronizing deterministic push-down automata can be really hard. In: Proceedings of the MFCS 2020. LIPIcs, pp. 33:1\u201333:15 (2020)"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Greibach, S.: Deterministic context free languages. Inform. Control 9, 620\u2013648 (1966)","journal-title":"Inform. Control"},{"key":"27_CR8","first-page":"429","volume":"4","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Spanier, E.H.: Finite-turn pushdown automata. SIAM J. Comput. 4, 429\u2013453 (1966)","journal-title":"SIAM J. Comput."},{"key":"27_CR9","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1145\/321356.321365","volume":"13","author":"SA Greibach","year":"1966","unstructured":"Greibach, S.A.: The unsolvability of the recognition of linear context-free languages. J. ACM 13, 582\u2013587 (1966)","journal-title":"J. ACM"},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/321495.321503","volume":"16","author":"SA Greibach","year":"1969","unstructured":"Greibach, S.A.: An infinite hierarchy of context-free languages. J. ACM 16, 91\u2013106 (1969)","journal-title":"J. ACM"},{"key":"27_CR11","unstructured":"Hopcroft, J. E., Ullman, J. D.: Formal Languages and Their Relation to Automata. Addison-Wesley Educational Publishers, Boston (1969)"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","volume":"8","author":"DE Knuth","year":"1965","unstructured":"Knuth, D.E.: On the translation of languages from left to right. Inform. Control 8, 607\u2013639 (1965)","journal-title":"Inform. Control"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"2152","DOI":"10.1016\/j.dam.2007.05.021","volume":"155","author":"M Kutrib","year":"2007","unstructured":"Kutrib, M., Malcher, A.: Finite turns and the regular closure of linear context-free languages. Discret. Appl. Math. 155, 2152\u20132164 (2007)","journal-title":"Discret. Appl. Math."},{"key":"27_CR14","first-page":"265","volume":"12","author":"A Malcher","year":"2007","unstructured":"Malcher, A.: On recursive and non-recursive trade-offs between finite-turn pushdown automata. J. Autom. Lang. Comb. 12, 265\u2013277 (2007)","journal-title":"J. Autom. Lang. Comb."},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"1303","DOI":"10.1142\/S0129054107005340","volume":"18","author":"E Magalini","year":"2007","unstructured":"Magalini, E., Pighizzini, G.: A pumping condition for ultralinear languages. Int. J. Found. Comput. Sci. 18, 1303\u20131312 (2007)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1080\/0020716022000005564","volume":"80","author":"E Moriya","year":"2003","unstructured":"Moriya, E., Tada, T.: On the space complexity of turn bounded pushdown automata. Int. J. Comput. Math. 80, 295\u2013304 (2003)","journal-title":"Int. J. Comput. Math."},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/978-3-642-12200-2_10","volume-title":"LATIN 2010: Theoretical Informatics","author":"S La Torre","year":"2010","unstructured":"La Torre, S., Madhusudan, P., Parlato, G.: The language theory of bounded context-switching. In: L\u00f3pez-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 96\u2013107. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12200-2_10"},{"key":"27_CR18","unstructured":"Valiant, L.G.: Decision procedures for families of determinsitic pushdown automata. Ph.D. Dissertation, University of Warwick (1973)"},{"key":"27_CR19","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/S0019-9958(74)90839-0","volume":"25","author":"LG Valiant","year":"1974","unstructured":"Valiant, L.G.: The equivalence problem for determinsitic finite-turn pushdown automata. Inform. Control 25, 123\u2013133 (1974)","journal-title":"Inform. Control"},{"key":"27_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/978-3-030-10801-4_40","volume-title":"SOFSEM 2019: Theory and Practice of Computer Science","author":"T Yamakami","year":"2019","unstructured":"Yamakami, T.: Behavioral strengths and weaknesses of various models of limited automata. In: Catania, B., Kr\u00e1lovi\u010d, R., Nawrocki, J., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 519\u2013530. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_40"},{"key":"27_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/978-3-030-40608-0_24","volume-title":"Language and Automata Theory and Applications","author":"T Yamakami","year":"2020","unstructured":"Yamakami, T.: Intersection and union hierarchies of deterministic context-free languages and pumping lemmas. In: Leporati, A., Mart\u00edn-Vide, C., Shapira, D., Zandron, C. (eds.) LATA 2020. LNCS, vol. 12038, pp. 341\u2013353. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-40608-0_24"},{"key":"27_CR22","unstructured":"Yamakami, T.: The no endmarker theorem for one-way probabilistic pushdown automata. Manuscript, available at arXiv:2111.02688 (2021)"},{"key":"27_CR23","doi-asserted-by":"publisher","unstructured":"Yamakami, T., Mikami, E.: Synchronizing words for real-time deterministic pushdown automata. In: Giri, D., Raymond Choo, K.K., Ponnusamy, S., Meng, W., Akleylek, S., Prasad Maity, S. (eds.) Proceedings of the Seventh International Conference on Mathematics and Computing. AISC, vol. 1412, pp. 551\u2013562. Springer, Singapore (2022). https:\/\/doi.org\/10.1007\/978-981-16-6890-6_41","DOI":"10.1007\/978-981-16-6890-6_41"},{"key":"27_CR24","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0020-0190(89)90108-7","volume":"31","author":"S Yu","year":"1989","unstructured":"Yu, S.: A pumping lemma for deterministic context-free languages. Inform. Process. Lett. 31, 47\u201351 (1989)","journal-title":"Inform. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-17715-6_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,2]],"date-time":"2022-10-02T23:05:32Z","timestamp":1664751932000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-17715-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031177149","9783031177156"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-17715-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"3 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ICTAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Theoretical Aspects of Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tbilisi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Georgia","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":"27 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ictac2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/viam.science.tsu.ge\/clas2022\/ictac\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}