{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T17:36:21Z","timestamp":1725730581975},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387708"},{"type":"electronic","value":"9783642387715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38771-5_25","type":"book-chapter","created":{"date-parts":[[2013,6,9]],"date-time":"2013-06-09T22:16:25Z","timestamp":1370816185000},"page":"277-288","source":"Crossref","is-referenced-by-count":1,"title":["Unambiguous Conjunctive Grammars over a One-Letter Alphabet"],"prefix":"10.1007","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/978-3-642-20712-9_27","volume-title":"Computer Science \u2013 Theory and Applications","author":"T. Aizikowitz","year":"2011","unstructured":"Aizikowitz, T., Kaminski, M.: LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 345\u2013358. Springer, Heidelberg (2011)"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Allouche, J.-P., Shallit, J.: Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press (2003)","DOI":"10.1017\/CBO9780511546563"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, Salomaa (eds.) Handbook of Formal Languages, vol.\u00a01, pp. 111\u2013174. Springer (1997)","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Culik II, K., Gruska, J., Salomaa, A.: Systolic trellis automata, I and II. International Journal of Computer Mathematics\u00a015, 16, 195\u2013212, 3\u201322 (1984)","DOI":"10.1080\/00207168408803421"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0166-218X(94)90146-5","volume":"52","author":"P. Enflo","year":"1994","unstructured":"Enflo, P., Granville, A., Shallit, J., Yu, S.: On sparse languages L such that LL\u2009=\u2009\u03a3*. Discrete Applied Mathematics\u00a052, 275\u2013285 (1994)","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0304-3975(84)90015-X","volume":"29","author":"O.H. Ibarra","year":"1984","unstructured":"Ibarra, O.H., Kim, S.M.: Characterizations and computational complexity of systolic trellis automata. Theoretical Computer Science\u00a029, 123\u2013153 (1984)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"25_CR7","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. International Journal of Foundations of Computer Science\u00a019(3), 597\u2013615 (2008)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"1","key":"25_CR8","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 of Computing Systems\u00a046(1), 27\u201358 (2010)","journal-title":"Theory of Computing Systems"},{"issue":"2","key":"25_CR9","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s00224-009-9246-y","volume":"48","author":"A. Je\u017c","year":"2011","unstructured":"Je\u017c, A., Okhotin, A.: Complexity of equations over sets of natural numbers. Theory of Computing Systems\u00a048(2), 319\u2013342 (2011)","journal-title":"Theory of Computing Systems"},{"key":"25_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/978-3-540-70583-3_6","volume-title":"Automata, Languages and Programming","author":"A. Je\u017c","year":"2008","unstructured":"Je\u017c, A., Okhotin, A.: On the computational completeness of equations over sets of natural numbers. In: Aceto, L., et al. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 63\u201374. Springer, Heidelberg (2008)"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-642-31623-4_14","volume-title":"Descriptional Complexity of Formal Systems","author":"A. Je\u017c","year":"2012","unstructured":"Je\u017c, A., Okhotin, A.: On the number of nonterminal symbols in unambiguous conjunctive grammars. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol.\u00a07386, pp. 183\u2013195. Springer, Heidelberg (2012)"},{"issue":"9","key":"25_CR12","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. Information and Computation\u00a0207(9), 945\u2013967 (2009)","journal-title":"Information and Computation"},{"key":"25_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-540-73208-2_3","volume-title":"Developments in Language Theory","author":"M. Kunc","year":"2007","unstructured":"Kunc, M.: What do we know about language equations? In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 23\u201327. Springer, Heidelberg (2007)"},{"key":"25_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00037-007-0229-6","volume":"16","author":"P. McKenzie","year":"2007","unstructured":"McKenzie, P., Wagner, K.W.: The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity\u00a016, 211\u2013244 (2007)","journal-title":"Computational Complexity"},{"key":"25_CR15","first-page":"519","volume":"4","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics\u00a04, 519\u2013535 (2001)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"1","key":"25_CR16","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\u00a038(1), 69\u201388 (2004)","journal-title":"Informatique Th\u00e9orique et Applications"},{"key":"25_CR17","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. Information and Computation\u00a0206, 1234\u20131247 (2008)","journal-title":"Information and Computation"},{"issue":"3-4","key":"25_CR18","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. Journal of Computer and System Sciences\u00a076(3-4), 251\u2013266 (2010)","journal-title":"Journal of Computer and System Sciences"},{"key":"25_CR19","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)"},{"key":"25_CR20","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2012.06.032","volume":"457","author":"A. Okhotin","year":"2012","unstructured":"Okhotin, A., Reitwie\u00dfner, C.: Parsing Boolean grammars over a one-letter alphabet using online convolution. Theoretical Computer Science\u00a0457, 149\u2013157 (2012)","journal-title":"Theoretical Computer Science"},{"key":"25_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2012.01.004","volume":"212","author":"A. Okhotin","year":"2012","unstructured":"Okhotin, A., Rondogiannis, P.: On the expressive power of univariate equations over sets of natural numbers. Information and Computation\u00a0212, 1\u201314 (2012)","journal-title":"Information and Computation"},{"key":"25_CR22","first-page":"50","volume":"212","author":"A.L. Semenov","year":"1973","unstructured":"Semenov, A.L.: Algorithmic problems for power series and for context-free grammars. Doklady Akademii Nauk SSSR\u00a0212, 50\u201352 (1973)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"25_CR23","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. Theoretical Computer Science\u00a0141, 331\u2013335 (1995)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38771-5_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T20:22:31Z","timestamp":1557778951000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38771-5_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387708","9783642387715"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38771-5_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}