{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T18:47:11Z","timestamp":1769971631817,"version":"3.49.0"},"publisher-location":"Cham","reference-count":91,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319773124","type":"print"},{"value":"9783319773131","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-77313-1_3","type":"book-chapter","created":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T21:20:49Z","timestamp":1520371249000},"page":"36-59","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Underlying Principles and Recurring Ideas of Formal Grammars"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,8]]},"reference":[{"issue":"3","key":"3_CR1","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1007\/978-3-540-69937-8_6","volume":"50","author":"T Aizikowitz","year":"2013","unstructured":"Aizikowitz, T., Kaminski, M.: Conjunctive grammars and alternating pushdown automata. Acta Informatica 50(3), 175\u2013197 (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-540-69937-8_6","journal-title":"Acta Informatica"},{"issue":"8","key":"3_CR2","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1016\/j.jcss.2016.05.008","volume":"82","author":"T Aizikowitz","year":"2016","unstructured":"Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. J. Comput. Syst. Sci. 82(8), 1329\u20131359 (2016). \nhttps:\/\/doi.org\/10.1016\/j.jcss.2016.05.008","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1516512.1516518","volume":"56","author":"R Alur","year":"2009","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56, 3 (2009). \nhttps:\/\/doi.org\/10.1145\/1516512.1516518","journal-title":"J. ACM"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1145\/322307.322315","volume":"29","author":"C Bader","year":"1982","unstructured":"Bader, C., Moura, A.: A generalization of Ogden\u2019s lemma. J. ACM 29(2), 404\u2013407 (1982). \nhttps:\/\/doi.org\/10.1145\/322307.322315","journal-title":"J. ACM"},{"key":"3_CR5","first-page":"155","volume":"9F","author":"Y Bar-Hillel","year":"1960","unstructured":"Bar-Hillel, Y., Gaifman, H., Shamir, E.: On categorial and phrase structure grammars. Bull. Res. Counc. Israel 9F, 155\u2013166 (1960)","journal-title":"Bull. Res. Counc. Israel"},{"key":"3_CR6","first-page":"143","volume":"14","author":"Y Bar-Hillel","year":"1961","unstructured":"Bar-Hillel, Y., Perles, M., Shamir, E.: On formal properties of simple phrase-structure grammars. Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung 14, 143\u2013177 (1961)","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1016\/j.ic.2014.03.003","volume":"237","author":"M Barash","year":"2014","unstructured":"Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268\u2013293 (2014). \nhttps:\/\/doi.org\/10.1016\/j.ic.2014.03.003","journal-title":"Inf. Comput."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.tcs.2015.05.004","volume":"591","author":"M Barash","year":"2015","unstructured":"Barash, M., Okhotin, A.: Two-sided context specifications in formal grammars. Theoret. Comput. Sci. 591, 134\u2013153 (2015). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2015.05.004","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/3-540-45711-9_1","volume-title":"Formal and Natural Computing","author":"J Berstel","year":"2002","unstructured":"Berstel, J., Boasson, L.: Balanced grammars and their languages. In: Brauer, W., Ehrig, H., Karhum\u00e4ki, J., Salomaa, A. (eds.) Formal and Natural Computing. LNCS, vol. 2300, pp. 3\u201325. Springer, Heidelberg (2002). \nhttps:\/\/doi.org\/10.1007\/3-540-45711-9_1"},{"issue":"1","key":"3_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0304-3975(82)90128-1","volume":"17","author":"M Blattner","year":"1982","unstructured":"Blattner, M., Ginsburg, S.: Position-restricted grammar forms and grammars. Theoret. Comput. Sci. 17(1), 1\u201327 (1982). \nhttps:\/\/doi.org\/10.1016\/0304-3975(82)90128-1","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR11","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0304-3975(82)90122-0","volume":"27","author":"N Blum","year":"1983","unstructured":"Blum, N.: More on the power of chain rules in context-free grammars. Theoret. Comput. Sci. 27, 287\u2013295 (1983). \nhttps:\/\/doi.org\/10.1016\/0304-3975(82)90122-0","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/BF01768473","volume":"11","author":"L Boasson","year":"1977","unstructured":"Boasson, L., Nivat, M.: Le cylindre des langages lin\u00e9aires. Math. Syst. Theory 11, 147\u2013155 (1977). \nhttps:\/\/doi.org\/10.1007\/BF01768473","journal-title":"Math. Syst. Theory"},{"issue":"2\u20133","key":"3_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1023\/A:1009907814595","volume":"3","author":"P Boullier","year":"2000","unstructured":"Boullier, P.: A cubic time extension of context-free grammars. Grammars 3(2\u20133), 111\u2013131 (2000). \nhttps:\/\/doi.org\/10.1023\/A:1009907814595","journal-title":"Grammars"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-0208(08)73072-X","volume":"102","author":"B Braunm\u00fchl von","year":"1985","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input driven languages are recognized in \n            $$\\log n$$\n           space. North-Holland Math. Stud. 102, 1\u201319 (1985). \nhttps:\/\/doi.org\/10.1016\/S0304-0208(08)73072-X","journal-title":"North-Holland Math. Stud."},{"issue":"7","key":"3_CR15","first-page":"7.1","volume":"6","author":"RP Brent","year":"1984","unstructured":"Brent, R.P., Goldschlager, L.M.: A parallel algorithm for context-free parsing. Aust. Comput. Sci. Commun. 6(7), 7.1\u20137.10 (1984)","journal-title":"Aust. Comput. Sci. Commun."},{"issue":"4","key":"3_CR16","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s002360050123","volume":"35","author":"T Buchholz","year":"1998","unstructured":"Buchholz, T., Kutrib, M.: On time computability of functions in one-way cellular automata. Acta Informatica 35(4), 329\u2013352 (1998). \nhttps:\/\/doi.org\/10.1007\/s002360050123","journal-title":"Acta Informatica"},{"issue":"3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1109\/TIT.1956.1056813","volume":"2","author":"N Chomsky","year":"1956","unstructured":"Chomsky, N.: Three models for the description of language. IRE Trans. Inf. Theory 2(3), 113\u2013124 (1956). \nhttps:\/\/doi.org\/10.1109\/TIT.1956.1056813","journal-title":"IRE Trans. Inf. Theory"},{"key":"3_CR18","doi-asserted-by":"publisher","unstructured":"Chomsky, N., Sch\u00fctzenberger, M.P.: The algebraic theory of context-free languages, In: Braffort, H. (ed.) Computer Programming and Formal Systems, pp. 118\u2013161. North-Holland, Amsterdam (1963). \nhttps:\/\/doi.org\/10.1016\/S0049-237X(08)72023-8","DOI":"10.1016\/S0049-237X(08)72023-8"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/BFb0016233","volume-title":"Mathematical Foundations of Computer Science 1986","author":"MP Chytil","year":"1986","unstructured":"Chytil, M.P.: Kins of context-free languages. In: Gruska, J., Rovan, B., Wiedermann, J. (eds.) MFCS 1986. LNCS, vol. 233, pp. 44\u201358. Springer, Heidelberg (1986). \nhttps:\/\/doi.org\/10.1007\/BFb0016233"},{"key":"3_CR20","unstructured":"Clark, A., Eyraud, R., Habrard, A.: Using contextual representations to efficiently learn context-freelanguages. J. Mach. Learn. Res. 11, 2707\u20132744 (2010). \nhttp:\/\/www.jmlr.org\/papers\/v11\/clark10a.html"},{"key":"3_CR21","doi-asserted-by":"publisher","unstructured":"Cook, S.A.: Deterministic CFL\u2019s are accepted simultaneously in polynomial time and log squared space. In: 11th Annual ACM Symposium on Theory of Computing, (STOC 1979, 30 April\u20132 May 1979, Atlanta, Georgia, USA), pp. 338\u2013345 (1979). \nhttps:\/\/doi.org\/10.1145\/800135.804426","DOI":"10.1145\/800135.804426"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-319-30000-9_27","volume-title":"Language and Automata Theory and Applications","author":"S Crespi Reghizzi","year":"2016","unstructured":"Crespi Reghizzi, S., San Pietro, P.: The missing case in Chomsky-Sch\u00fctzenberger theorem. In: Dediu, A.-H., Janou\u0161ek, J., Mart\u00edn-Vide, C., Truthe, B. (eds.) LATA 2016. LNCS, vol. 9618, pp. 345\u2013358. Springer, Cham (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-30000-9_27"},{"issue":"8","key":"3_CR23","doi-asserted-by":"publisher","first-page":"955","DOI":"10.1142\/S0129054114400176","volume":"25","author":"M Droste","year":"2014","unstructured":"Droste, M., Vogler, H.: The Chomsky-Sch\u00fctzenberger theorem for quantitative context-free languages. Int. J. Found. Comput. Sci. 25(8), 955\u2013970 (2014). \nhttps:\/\/doi.org\/10.1142\/S0129054114400176","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"6","key":"3_CR24","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0020-0190(92)90101-Z","volume":"44","author":"J Engelfriet","year":"1992","unstructured":"Engelfriet, J.: An elementary proof of double Greibach normal form. Inf. Process. Lett. 44(6), 291\u2013293 (1992). \nhttps:\/\/doi.org\/10.1016\/0020-0190(92)90101-Z","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"3_CR25","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.ipl.2011.03.019","volume":"111","author":"J Esparza","year":"2011","unstructured":"Esparza, J., Ganty, P., Kiefer, S., Luttenberger, M.: Parikh\u2019s theorem: a simple and direct automaton construction. Inf. Process. Lett. 111(12), 614\u2013619 (2011). \nhttps:\/\/doi.org\/10.1016\/j.ipl.2011.03.019","journal-title":"Inf. Process. Lett."},{"key":"3_CR26","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/0304-3975(87)90011-9","volume":"49","author":"P Flajolet","year":"1987","unstructured":"Flajolet, P.: Analytic models and ambiguity of context-free languages. Theoret. Comput. Sci. 49, 283\u2013309 (1987). \nhttps:\/\/doi.org\/10.1016\/0304-3975(87)90011-9","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"3_CR27","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/321172.321179","volume":"10","author":"RW Floyd","year":"1963","unstructured":"Floyd, R.W.: Syntactic analysis and operator precedence. J. ACM 10(3), 316\u2013333 (1963). \nhttps:\/\/doi.org\/10.1145\/321172.321179","journal-title":"J. ACM"},{"issue":"6","key":"3_CR28","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.A.: Deterministic context-free languages. Inf. Control 9(6), 620\u2013648 (1966). \nhttps:\/\/doi.org\/10.1016\/S0019-9958(66)80019-0","journal-title":"Inf. Control"},{"issue":"2","key":"3_CR29","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1145\/321386.321403","volume":"14","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Greibach, S.A., Harrison, M.A.: One-way stack automata. J. ACM 14(2), 389\u2013418 (1967). \nhttps:\/\/doi.org\/10.1145\/321386.321403","journal-title":"J. ACM"},{"issue":"1","key":"3_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-0000(67)80003-5","volume":"1","author":"S Ginsburg","year":"1967","unstructured":"Ginsburg, S., Harrison, M.A.: Bracketed context-free languages. J. Comput. Syst. Sci. 1(1), 1\u201323 (1967). \nhttps:\/\/doi.org\/10.1016\/S0022-0000(67)80003-5","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR31","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1145\/321127.321132","volume":"9","author":"S Ginsburg","year":"1962","unstructured":"Ginsburg, S., Rice, H.G.: Two families of languages related to ALGOL. J. ACM 9, 350\u2013371 (1962). \nhttps:\/\/doi.org\/10.1145\/321127.321132","journal-title":"J. ACM"},{"key":"3_CR32","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/321250.321254","volume":"12","author":"SA Greibach","year":"1965","unstructured":"Greibach, S.A.: A new normal-form theorem for context-free phrase structure grammars. J. ACM 12, 42\u201352 (1965). \nhttps:\/\/doi.org\/10.1145\/321250.321254","journal-title":"J. ACM"},{"issue":"4","key":"3_CR33","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"SA Greibach","year":"1973","unstructured":"Greibach, S.A.: The hardest context-free language. SIAM J. Comput. 2(4), 304\u2013310 (1973). \nhttps:\/\/doi.org\/10.1137\/0202025","journal-title":"SIAM J. Comput."},{"issue":"2","key":"3_CR34","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1137\/0203009","volume":"3","author":"SA Greibach","year":"1974","unstructured":"Greibach, S.A.: Jump PDA\u2019s and hierarchies of deterministic context-free languages. SIAM J. Comput. 3(2), 111\u2013127 (1974). \nhttps:\/\/doi.org\/10.1137\/0203009","journal-title":"SIAM J. Comput."},{"key":"3_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/3-540-57163-9_25","volume-title":"Fundamentals of Computation Theory","author":"M Holzer","year":"1993","unstructured":"Holzer, M., Lange, K.-J.: On the complexities of linear LL(1) and LR(1) grammars. In: \u00c9sik, Z. (ed.) FCT 1993. LNCS, vol. 710, pp. 299\u2013308. Springer, Heidelberg (1993). \nhttps:\/\/doi.org\/10.1007\/3-540-57163-9_25"},{"key":"3_CR36","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(84)90015-X","volume":"29","author":"OH Ibarra","year":"1984","unstructured":"Ibarra, O.H., Kim, S.M.: Characterizations and computational complexity of systolic trellis automata. Theoret. Comput. Sci. 29, 123\u2013153 (1984). \nhttps:\/\/doi.org\/10.1016\/0304-3975(84)90015-X","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"3_CR37","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N Immerman","year":"1986","unstructured":"Immerman, N.: Relational queries computable in polynomial time. Inf. Control 68(1\u20133), 86\u2013104 (1986). \nhttps:\/\/doi.org\/10.1016\/S0019-9958(86)80029-8","journal-title":"Inf. Control"},{"key":"3_CR38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5","volume-title":"Descriptive Complexity","author":"N Immerman","year":"1999","unstructured":"Immerman, N.: Descriptive Complexity. Springer, New York (1999). \nhttps:\/\/doi.org\/10.1007\/978-1-4612-0539-5"},{"issue":"3","key":"3_CR39","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1142\/S012905410800584X","volume":"19","author":"A Je\u017c","year":"2008","unstructured":"Je\u017c, A.: Conjunctive grammars can generate non-regular unary languages. Int. J. Found. Comput. Sci. 19(3), 597\u2013615 (2008). \nhttps:\/\/doi.org\/10.1142\/S012905410800584X","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"3_CR40","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/s00224-008-9139-5","volume":"46","author":"A Je\u017c","year":"2010","unstructured":"Je\u017c, A., Okhotin, A.: Conjunctive grammars over a unary alphabet: undecidability and unbounded growth. Theory Comput. Syst. 46(1), 27\u201358 (2010). \nhttps:\/\/doi.org\/10.1007\/s00224-008-9139-5","journal-title":"Theory Comput. Syst."},{"key":"3_CR41","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ic.2014.05.001","volume":"237","author":"A Je\u017c","year":"2014","unstructured":"Je\u017c, A., Okhotin, A.: Computational completeness of equations over sets of natural numbers. Inf. Comput. 237, 56\u201394 (2014). \nhttps:\/\/doi.org\/10.1016\/j.ic.2014.05.001","journal-title":"Inf. Comput."},{"key":"3_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1007\/978-3-642-02737-6_25","volume-title":"Developments in Language Theory","author":"M Kanazawa","year":"2009","unstructured":"Kanazawa, M.: The pumping lemma for well-nested multiple context-free languages. In: Diekert, V., Nowotka, D. (eds.) DLT 2009. LNCS, vol. 5583, pp. 312\u2013325. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-02737-6_25"},{"issue":"1","key":"3_CR43","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/s00224-014-9534-z","volume":"55","author":"M Kanazawa","year":"2014","unstructured":"Kanazawa, M., Kobele, G.M., Michaelis, J., Salvati, S., Yoshinaka, R.: The failure of the strong pumping lemma for multiple context-free languages. Theory Comput. Syst. 55(1), 250\u2013278 (2014). \nhttps:\/\/doi.org\/10.1007\/s00224-014-9534-z","journal-title":"Theory Comput. Syst."},{"issue":"3","key":"3_CR44","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0304-3975(83)90026-9","volume":"28","author":"A Kelemenov\u00e1","year":"1983","unstructured":"Kelemenov\u00e1, A.: Complexity of normal form grammars. Theoret. Comput. Sci. 28(3), 299\u2013314 (1983). \nhttps:\/\/doi.org\/10.1016\/0304-3975(83)90026-9","journal-title":"Theoret. Comput. Sci."},{"issue":"9","key":"3_CR45","doi-asserted-by":"publisher","first-page":"945","DOI":"10.1016\/j.ic.2009.05.002","volume":"207","author":"V Kountouriotis","year":"2009","unstructured":"Kountouriotis, V., Nomikos, C., Rondogiannis, P.: Well-founded semantics for Boolean grammars. Inf. Comput. 207(9), 945\u2013967 (2009). \nhttps:\/\/doi.org\/10.1016\/j.ic.2009.05.002","journal-title":"Inf. Comput."},{"key":"3_CR46","volume-title":"Logic for Problem Solving","author":"R Kowalski","year":"1979","unstructured":"Kowalski, R.: Logic for Problem Solving. North-Holland, Amsterdam (1979)"},{"issue":"4","key":"3_CR47","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/s00224-006-1321-z","volume":"40","author":"M Kunc","year":"2007","unstructured":"Kunc, M.: The power of commuting with finite sets of words. Theory Comput. Syst. 40(4), 521\u2013551 (2007). \nhttps:\/\/doi.org\/10.1007\/s00224-006-1321-z","journal-title":"Theory Comput. Syst."},{"key":"3_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-642-39998-5_15","volume-title":"Formal Grammar","author":"S Kuznetsov","year":"2013","unstructured":"Kuznetsov, S.: Conjunctive grammars in Greibach normal form and the Lambek calculus with additive connectives. In: Morrill, G., Nederhof, M.-J. (eds.) FG 2012-2013. LNCS, vol. 8036, pp. 242\u2013249. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-39998-5_15"},{"key":"3_CR49","doi-asserted-by":"crossref","unstructured":"Kuznetsov, S., Okhotin, A.: Conjunctive categorial grammars. In: Proceedings of 15th Meeting on the Mathematics of Language (MOL 2017, London, UK, 13\u201314 July 2017), pp. 141\u2013151. ACL (2017)","DOI":"10.18653\/v1\/W17-3414"},{"issue":"2","key":"3_CR50","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/S1571-0661(05)80365-2","volume":"68","author":"M Lange","year":"2002","unstructured":"Lange, M.: Alternating context-free languages and linear time \n            $$\\mu $$\n          -calculus with sequential composition. Electron. Notes Theoret. Comput. Sci. 68(2), 70\u201386 (2002). \nhttps:\/\/doi.org\/10.1016\/S1571-0661(05)80365-2","journal-title":"Electron. Notes Theoret. Comput. Sci."},{"issue":"5","key":"3_CR51","doi-asserted-by":"publisher","first-page":"799","DOI":"10.1142\/S0129054110007568","volume":"21","author":"T Lehtinen","year":"2010","unstructured":"Lehtinen, T., Okhotin, A.: Boolean grammars and GSM mappings. Int. J. Found. Comput. Sci. 21(5), 799\u2013815 (2010). \nhttps:\/\/doi.org\/10.1142\/S0129054110007568","journal-title":"Int. J. Found. Comput. Sci."},{"key":"3_CR52","doi-asserted-by":"publisher","unstructured":"Lewis II, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: IEEE Conference Record on Switching Circuit Theory and Logical Design, pp. 191\u2013202 (1965). \nhttps:\/\/doi.org\/10.1109\/FOCS.1965.14","DOI":"10.1109\/FOCS.1965.14"},{"issue":"3","key":"3_CR53","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R McNaughton","year":"1967","unstructured":"McNaughton, R.: Parenthesis grammars. J. ACM 14(3), 490\u2013500 (1967). \nhttps:\/\/doi.org\/10.1145\/321406.321411","journal-title":"J. ACM"},{"key":"3_CR54","unstructured":"Nakanishi, R., Takada, K., Nii, H., Seki, H.: Efficient recognition algorithms for parallel multiple context-free languages and for multiple context-free languages. IEICE Trans. Inf. Syst. E81-D:11, 1148\u20131161 (1998)"},{"issue":"3","key":"3_CR55","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01694004","volume":"2","author":"WF Ogden","year":"1968","unstructured":"Ogden, W.F.: A helpful result for proving inherent ambiguity. Math. Syst. Theory 2(3), 191\u2013194 (1968). \nhttps:\/\/doi.org\/10.1007\/BF01694004","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"3_CR56","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0214031","volume":"14","author":"W Ogden","year":"1985","unstructured":"Ogden, W., Ross, R.J., Winklmann, K.: An \u2018interchange lemma\u2019 for context-free languages. SIAM J. Comput. 14(2), 410\u2013415 (1985). \nhttps:\/\/doi.org\/10.1137\/0214031","journal-title":"SIAM J. Comput."},{"issue":"4","key":"3_CR57","first-page":"519","volume":"6","author":"A Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. J. Automata Lang. Comb. 6(4), 519\u2013535 (2001)","journal-title":"J. Automata Lang. Comb."},{"issue":"1","key":"3_CR58","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ic.2004.03.006","volume":"194","author":"A Okhotin","year":"2004","unstructured":"Okhotin, A.: Boolean grammars. Inf. Comput. 194(1), 19\u201348 (2004). \nhttps:\/\/doi.org\/10.1016\/j.ic.2004.03.006","journal-title":"Inf. Comput."},{"issue":"1","key":"3_CR59","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1051\/ita:2004004","volume":"38","author":"A Okhotin","year":"2004","unstructured":"Okhotin, A.: On the equivalence of linear conjunctive grammars to trellis automata. Informatique Th\u00e9orique et Applications 38(1), 69\u201388 (2004). \nhttps:\/\/doi.org\/10.1051\/ita:2004004","journal-title":"Informatique Th\u00e9orique et Applications"},{"issue":"3","key":"3_CR60","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.tcs.2005.07.037","volume":"349","author":"A Okhotin","year":"2005","unstructured":"Okhotin, A.: Unresolved systems of language equations: expressive power and decision problems. Theoret. Comput. Sci. 349(3), 283\u2013308 (2005). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2005.07.037","journal-title":"Theoret. Comput. Sci."},{"issue":"3\u20134","key":"3_CR61","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s00236-007-0045-0","volume":"44","author":"A Okhotin","year":"2007","unstructured":"Okhotin, A.: Recursive descent parsing for Boolean grammars. Acta Informatica 44(3\u20134), 167\u2013189 (2007). \nhttps:\/\/doi.org\/10.1007\/s00236-007-0045-0","journal-title":"Acta Informatica"},{"key":"3_CR62","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1016\/j.ic.2008.03.023","volume":"206","author":"A Okhotin","year":"2008","unstructured":"Okhotin, A.: Unambiguous Boolean grammars. Inf. Comput. 206, 1234\u20131247 (2008). \nhttps:\/\/doi.org\/10.1016\/j.ic.2008.03.023","journal-title":"Inf. Comput."},{"issue":"3\u20134","key":"3_CR63","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/j.jcss.2009.08.002","volume":"76","author":"A Okhotin","year":"2010","unstructured":"Okhotin, A.: Decision problems for language equations. J. Comput. Syst. Sci. 76(3\u20134), 251\u2013266 (2010). \nhttps:\/\/doi.org\/10.1016\/j.jcss.2009.08.002","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR64","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-31653-1_12","volume-title":"Developments in Language Theory","author":"A Okhotin","year":"2012","unstructured":"Okhotin, A.: Non-erasing variants of the Chomsky\u2013Sch\u00fctzenberger theorem. In: Yen, H.-C., Ibarra, O.H. (eds.) DLT 2012. LNCS, vol. 7410, pp. 121\u2013129. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-31653-1_12"},{"key":"3_CR65","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.cosrev.2013.06.001","volume":"9","author":"A Okhotin","year":"2013","unstructured":"Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Comput. Sci. Rev. 9, 27\u201359 (2013). \nhttps:\/\/doi.org\/10.1016\/j.cosrev.2013.06.001","journal-title":"Comput. Sci. Rev."},{"key":"3_CR66","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/j.tcs.2013.09.011","volume":"516","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A.: Parsing by matrix multiplication generalized to Boolean grammars. Theoret. Comput. Sci. 516, 101\u2013120 (2014). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2013.09.011","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-319-34171-2_24","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Okhotin","year":"2016","unstructured":"Okhotin, A.: The hardest language for conjunctive grammars. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 340\u2013351. Springer, Cham (2016). \nhttps:\/\/doi.org\/10.1007\/978-3-319-34171-2_24"},{"issue":"26\u201328","key":"3_CR68","doi-asserted-by":"publisher","first-page":"2559","DOI":"10.1016\/j.tcs.2010.03.015","volume":"411","author":"A Okhotin","year":"2010","unstructured":"Okhotin, A., Reitwie\u00dfner, C.: Conjunctive grammars with restricted disjunction. Theoret. Comput. Sci. 411(26\u201328), 2559\u20132571 (2010). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2010.03.015","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR69","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/2636805.2636821","volume":"45","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. SIGACT News 45(2), 47\u201367 (2014). \nhttps:\/\/doi.org\/10.1145\/2636805.2636821","journal-title":"SIGACT News"},{"key":"3_CR70","doi-asserted-by":"crossref","unstructured":"Pereira, F.C.N., Warren, D.H.D.: Parsing as deduction. In: 21st Annual Meeting of the Association for Computational Linguistics (ACL 1983, Cambridge, Massachusetts, USA, 15\u201317 June 1983), pp. 137\u2013144 (1983)","DOI":"10.3115\/981311.981338"},{"key":"3_CR71","unstructured":"Pollard, C.J.: Generalized phrase structure grammars, head grammars, and natural language. Ph.D. thesis, Stanford University (1984)"},{"issue":"1","key":"3_CR72","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1006\/jcss.1997.1537","volume":"56","author":"S Rajasekaran","year":"1998","unstructured":"Rajasekaran, S., Yooseph, S.: TAL recognition in \n            $$O(M(n^2))$$\n           time. J. Comput. Syst. Sci. 56(1), 83\u201389 (1998). \nhttps:\/\/doi.org\/10.1006\/jcss.1997.1537","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"3_CR73","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/321406.321412","volume":"14","author":"DJ Rosenkrantz","year":"1967","unstructured":"Rosenkrantz, D.J.: Matrix equations and normal forms for context-free grammars. J. ACM 14(3), 501\u2013507 (1967). \nhttps:\/\/doi.org\/10.1145\/321406.321412","journal-title":"J. ACM"},{"issue":"4","key":"3_CR74","first-page":"1","volume":"14","author":"WC Rounds","year":"1988","unstructured":"Rounds, W.C.: LFP: a logic for linguistic descriptions and an analysis of its complexity. Comput. Linguist. 14(4), 1\u20139 (1988)","journal-title":"Comput. Linguist."},{"key":"3_CR75","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"318","DOI":"10.1007\/3-540-16066-3_26","volume-title":"Computation Theory","author":"W Rytter","year":"1985","unstructured":"Rytter, W.: On the recognition of context-free languages. In: Skowron, A. (ed.) SCT 1984. LNCS, vol. 208, pp. 318\u2013325. Springer, Heidelberg (1985). \nhttps:\/\/doi.org\/10.1007\/3-540-16066-3_26"},{"key":"3_CR76","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0","volume-title":"Automata-Theoretic Aspects of Formal Power Series","author":"A Salomaa","year":"1978","unstructured":"Salomaa, A., Soittola, M.: Automata-Theoretic Aspects of Formal Power Series. Springer, New York (1978). \nhttps:\/\/doi.org\/10.1007\/978-1-4612-6264-0"},{"issue":"2","key":"3_CR77","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","volume":"88","author":"H Seki","year":"1991","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theoret. Comput. Sci. 88(2), 191\u2013229 (1991). \nhttps:\/\/doi.org\/10.1016\/0304-3975(91)90374-B","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR78","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2012","unstructured":"Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Cengage Learning, Boston (2012)","edition":"3"},{"issue":"2","key":"3_CR79","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(78)90080-7","volume":"7","author":"S Soko\u0142owski","year":"1978","unstructured":"Soko\u0142owski, S.: A method for proving programming languages non context-free. Inf. Process. Lett. 7(2), 151\u2013153 (1978). \nhttps:\/\/doi.org\/10.1016\/0020-0190(78)90080-7","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"3_CR80","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"IH Sudborough","year":"1975","unstructured":"Sudborough, I.H.: A note on tape-bounded complexity classes and linear context-free languages. J. ACM 22(4), 499\u2013500 (1975). \nhttps:\/\/doi.org\/10.1145\/321906.321913","journal-title":"J. ACM"},{"key":"3_CR81","unstructured":"Szabari, A.: Alternuj\u00face Z\u00e1sobn\u00edkov\u00e9 Automaty (Alternating Pushdown Automata). M.Sc. thesis, 45 p. Diploma work, University of Ko\u0161ice (Czechoslovakia) (1991). (in Slovak)"},{"issue":"1\u20132","key":"3_CR82","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/0304-3975(94)00212-2","volume":"141","author":"V Terrier","year":"1995","unstructured":"Terrier, V.: On real-time one-way cellular array. Theoret. Comput. Sci. 141(1\u20132), 331\u2013335 (1995). \nhttps:\/\/doi.org\/10.1016\/0304-3975(94)00212-2","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR83","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2017.05.041","volume":"692","author":"V Terrier","year":"2017","unstructured":"Terrier, V.: Recognition of poly-slender context-free languages by trellis automata. Theoret. Comput. Sci. 692, 1\u201324 (2017). \nhttps:\/\/doi.org\/10.1016\/j.tcs.2017.05.041","journal-title":"Theoret. Comput. Sci."},{"key":"3_CR84","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-319-58631-1_14","volume-title":"Cellular Automata and Discrete Complex Systems","author":"V Terrier","year":"2017","unstructured":"Terrier, V.: Some computational limits of trellis automata. In: Dennunzio, A., Formenti, E., Manzoni, L., Porreca, A.E. (eds.) AUTOMATA 2017. LNCS, vol. 10248, pp. 176\u2013186. Springer, Cham (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-58631-1_14"},{"key":"3_CR85","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(85)90173-2","volume":"40","author":"FJ Urbanek","year":"1985","unstructured":"Urbanek, F.J.: On Greibach normal form construction. Theoret. Comput. Sci. 40, 315\u2013317 (1985). \nhttps:\/\/doi.org\/10.1016\/0304-3975(85)90173-2","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"3_CR86","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10(2), 308\u2013314 (1975). \nhttps:\/\/doi.org\/10.1016\/S0022-0000(75)80046-8","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR87","doi-asserted-by":"publisher","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: STOC 1982, pp. 137\u2013146 (1982). \nhttps:\/\/doi.org\/10.1109\/SFCS.1981.18","DOI":"10.1109\/SFCS.1981.18"},{"issue":"6","key":"3_CR88","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/BF01191624","volume":"27","author":"K Vijay-Shanker","year":"1994","unstructured":"Vijay-Shanker, K., Weir, D.J.: The equivalence of four extensions of context-free grammars. Math. Syst. Theory 27(6), 511\u2013546 (1994). \nhttps:\/\/doi.org\/10.1007\/BF01191624","journal-title":"Math. Syst. Theory"},{"key":"3_CR89","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D.J., Joshi, A.K.: Characterizing structural descriptions produced by various grammatical formalisms. In: 25th Annual Meeting of Association for Computational Linguistics (ACL 1987), pp. 104\u2013111 (1987)","DOI":"10.3115\/981175.981190"},{"key":"3_CR90","doi-asserted-by":"publisher","unstructured":"Yoshinaka, R.: Distributional learning of conjunctive grammars and contextual binary feature grammars. J. Comput. Syst. Sci. (to appear). \nhttps:\/\/doi.org\/10.1016\/j.jcss.2017.07.004","DOI":"10.1016\/j.jcss.2017.07.004"},{"key":"3_CR91","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/978-3-642-13089-2_50","volume-title":"Language and Automata Theory and Applications","author":"R Yoshinaka","year":"2010","unstructured":"Yoshinaka, R., Kaji, Y., Seki, H.: Chomsky-Sch\u00fctzenberger-type characterization of multiple context-free languages. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 596\u2013607. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-13089-2_50"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77313-1_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,3,6]],"date-time":"2018-03-06T21:22:25Z","timestamp":1520371345000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-77313-1_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319773124","9783319773131"],"references-count":91,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77313-1_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]}}}