{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T17:49:19Z","timestamp":1725731359766},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642393099"},{"type":"electronic","value":"9783642393105"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39310-5_20","type":"book-chapter","created":{"date-parts":[[2013,6,14]],"date-time":"2013-06-14T01:33:15Z","timestamp":1371173595000},"page":"205-216","source":"Crossref","is-referenced-by-count":3,"title":["Improved Normal Form for Grammars with One-Sided Contexts"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"20_CR1","first-page":"1209","volume":"11","author":"V.L. Arlazarov","year":"1970","unstructured":"Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradzhev, I.A.: On economical construction of the transitive closure of an oriented graph. Soviet Mathematics Doklady\u00a011, 1209\u20131210 (1970)","journal-title":"Soviet Mathematics Doklady"},{"key":"20_CR2","unstructured":"Barash, M.: Recursive descent parsing for grammars with contexts. SOFSEM 2013 student research forum (2013)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/978-3-642-28332-1_10","volume-title":"Language and Automata Theory and Applications","author":"M. Barash","year":"2012","unstructured":"Barash, M., Okhotin, A.: Defining contexts in context-free grammars. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 106\u2013118. Springer, Heidelberg (2012)"},{"key":"20_CR4","unstructured":"Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications, manuscript submitted for publication"},{"issue":"2","key":"20_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N. Chomsky","year":"1959","unstructured":"Chomsky, N.: On certain formal properties of grammars. Information and Control\u00a02(2), 137\u2013167 (1959)","journal-title":"Information and Control"},{"issue":"2","key":"20_CR6","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J. Earley","year":"1970","unstructured":"Earley, J.: An efficient context-free parsing algorithm. Communications of the ACM\u00a013(2), 94\u2013102 (1970)","journal-title":"Communications of the ACM"},{"issue":"3","key":"20_CR7","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1145\/357103.357112","volume":"2","author":"S.L. Graham","year":"1980","unstructured":"Graham, S.L., Harrison, M.A., Ruzzo, W.L.: An improved context-free recognizer. ACM Transactions of Programming Languages and Systems\u00a02(3), 415\u2013462 (1980)","journal-title":"ACM Transactions of Programming Languages and Systems"},{"issue":"4","key":"20_CR8","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics\u00a06(4), 519\u2013535 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"1","key":"20_CR9","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. Information and Computation\u00a0194(1), 19\u201348 (2004)","journal-title":"Information and Computation"},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-642-14455-4_31","volume-title":"Developments in Language Theory","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Fast parsing for Boolean grammars: A generalization of Valiant\u2019s algorithm. In: Gao, Y., Lu, H., Seki, S., Yu, S. (eds.) DLT 2010. LNCS, vol.\u00a06224, pp. 340\u2013351. Springer, Heidelberg (2010)"},{"issue":"4","key":"20_CR11","first-page":"1","volume":"14","author":"W.C. Rounds","year":"1988","unstructured":"Rounds, W.C.: LFP: A logic for linguistic descriptions and an analysis of its complexity. Computational Linguistics\u00a014(4), 1\u20139 (1988)","journal-title":"Computational Linguistics"},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L.G. Valiant","year":"1975","unstructured":"Valiant, L.G.: General context-free recognition in less than cubic time. Journal of Computer and System Sciences\u00a010(2), 308\u2013314 (1975)","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR13","unstructured":"Williams, R.: Matrix-vector multiplication in sub-quadratic time (some preprocessing required). In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, USA, January 7-9, pp. 995\u20131001 (2007)"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39310-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T03:47:30Z","timestamp":1557805650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39310-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642393099","9783642393105"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39310-5_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}