{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:02:37Z","timestamp":1769972557615,"version":"3.49.0"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,8,21]],"date-time":"2008-08-21T00:00:00Z","timestamp":1219276800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s00224-008-9139-5","type":"journal-article","created":{"date-parts":[[2008,8,20]],"date-time":"2008-08-20T16:10:30Z","timestamp":1219248630000},"page":"27-58","source":"Crossref","is-referenced-by-count":36,"title":["Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth"],"prefix":"10.1007","volume":"46","author":[{"given":"Artur","family":"Je\u017c","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,8,21]]},"reference":[{"key":"9139_CR1","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/978-3-642-59136-5_3","volume-title":"Handbook of Formal Languages","author":"J. Autebert","year":"1997","unstructured":"Autebert, J., Berstel, J., Boasson, L.: Context-free languages and pushdown automata. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol.\u00a01, pp. 111\u2013174. Springer, New York (1997)"},{"key":"9139_CR2","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theor. Comput. Sci. 47, 149\u2013158 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9139_CR3","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1080\/00207168408803410","volume":"15","author":"K. Culik II","year":"1984","unstructured":"Culik, K.\u00a0II, Gruska, J., Salomaa, A.: Systolic trellis automata,\u00a0I. Int. J. Comput. Math. 15, 195\u2013212 (1984)","journal-title":"Int. J. Comput. Math."},{"key":"9139_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1080\/00207168408803421","volume":"16","author":"K. Culik II","year":"1984","unstructured":"Culik, K.\u00a0II, Gruska, J., Salomaa, A.: Systolic trellis automata,\u00a0II. Int. J. Comput. Math. 16, 3\u201322 (1984)","journal-title":"Int. J. Comput. Math."},{"key":"9139_CR5","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/S0019-9958(86)80011-0","volume":"71","author":"K. Culik II","year":"1984","unstructured":"Culik, K.\u00a0II, Gruska, J., Salomaa, A.: Systolic trellis automata: stability, decidability and complexity. Inf. Control 71, 218\u2013230 (1984)","journal-title":"Inf. Control"},{"key":"9139_CR6","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/S0020-0190(02)00316-2","volume":"84","author":"M. Domaratzki","year":"2002","unstructured":"Domaratzki, M., Pighizzini, G., Shallit, J.: Simulating finite automata with context-free grammars. Inf. Process. Lett. 84, 339\u2013344 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9139_CR7","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"key":"9139_CR8","first-page":"42","volume-title":"Proceedings of Symposia in Applied Mathematics","author":"J. Hartmanis","year":"1967","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. In: Proceedings of Symposia in Applied Mathematics, vol.\u00a019, pp.\u00a042\u201351. Am. Math. Soc., Providence (1967)"},{"key":"9139_CR9","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 29, 123\u2013153 (1984)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9139_CR10","doi-asserted-by":"crossref","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)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9139_CR11","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/0304-3975(94)90227-5","volume":"132","author":"E.L. Leiss","year":"1994","unstructured":"Leiss, E.L.: Unrestricted complementation in language equations over a one-letter alphabet. Theor. Comput. Sci. 132, 71\u201393 (1994)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9139_CR12","first-page":"519","volume":"6","author":"A. Okhotin","year":"2001","unstructured":"Okhotin, A.: Conjunctive grammars. J. Autom. Lang. Comb. 6(4), 519\u2013535 (2001)","journal-title":"J. Autom. Lang. Comb."},{"key":"9139_CR13","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1023\/A:1020213411126","volume":"28","author":"A. Okhotin","year":"2002","unstructured":"Okhotin, A.: Conjunctive grammars and systems of language equations. Program. Comput. Softw. 28, 243\u2013249 (2002)","journal-title":"Program. Comput. Softw."},{"issue":"1","key":"9139_CR14","doi-asserted-by":"crossref","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. Inform. Th\u00e9or. Appl. 38(1), 69\u201388 (2004)","journal-title":"Inform. Th\u00e9or. Appl."},{"key":"9139_CR15","first-page":"96","volume":"91","author":"A. Okhotin","year":"2007","unstructured":"Okhotin, A.: Nine open problems for conjunctive and Boolean grammars. Bull. EATCS 91, 96\u2013119 (2007)","journal-title":"Bull. EATCS"},{"key":"9139_CR16","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/11779148_38","volume-title":"Developments in Language Theory","author":"A. Okhotin","year":"2006","unstructured":"Okhotin, A., Yakimova, O.: On language equations with complementation. In: Developments in Language Theory, DLT 2006, Santa Barbara, USA, June 26\u201329, 2006. LNCS, vol.\u00a04036, pp.\u00a0420\u2013432. Springer, Berlin (2006)"},{"key":"9139_CR17","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: STOC 1973, pp.\u00a01\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"9139_CR18","unstructured":"Wotschke, D.: Personal communication to A.\u00a0Okhotin, August 2000"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9139-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9139-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9139-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:36Z","timestamp":1558698696000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9139-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8,21]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9139"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9139-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8,21]]}}}