{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:42:56Z","timestamp":1725489776902},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540745921"},{"type":"electronic","value":"9783540745938"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74593-8_23","type":"book-chapter","created":{"date-parts":[[2007,8,22]],"date-time":"2007-08-22T11:00:40Z","timestamp":1187780440000},"page":"267-278","source":"Crossref","is-referenced-by-count":0,"title":["A Simple P-Complete Problem and Its Representations by Language Equations"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_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.\u00a0I, pp. 111\u2013174. Springer, Heidelberg (1997)"},{"issue":"1","key":"23_CR2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1145\/982962.964011","volume":"39","author":"Bryan Ford","year":"2004","unstructured":"Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. In: Proceedings of POPL 2004, Venice, Italy, January 14\u201316, 2004, pp. 111\u2013122 (2004)","journal-title":"ACM SIGPLAN Notices"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Galil, Z.: Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages. Mathematical Systems Theory\u00a010(3), 211\u2013228 (1977) (Earlier version In: 15th Annual Symposium on Automata and Switching Theory (1974))","DOI":"10.1007\/BF01683273"},{"key":"23_CR4","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. Journal of the ACM\u00a09, 350\u2013371 (1962)","journal-title":"Journal of the ACM"},{"issue":"2","key":"23_CR5","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The monotone and planar circuit value problems are log space complete for P. SIGACT News\u00a09(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"key":"23_CR6","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"23_CR7","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"},{"key":"23_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/11779148_19","volume-title":"Developments in Language Theory","author":"V. Kountouriotis","year":"2006","unstructured":"Kountouriotis, V., Nomikos, C., Rondogiannis, P.: Well-founded semantics for Boolean grammars. In: Ibarra, O.H., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 203\u2013214. Springer, Heidelberg (2006)"},{"issue":"1","key":"23_CR9","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is log space complete for P. SIGACT News\u00a07(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/11786986_13","volume-title":"Automata, Languages and Programming","author":"T. Neary","year":"2006","unstructured":"Neary, T., Woods, D.: P-completeness of cellular automaton rule 110. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 132\u2013143. Springer, Heidelberg (2006)"},{"issue":"4","key":"23_CR11","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"},{"key":"23_CR12","doi-asserted-by":"publisher","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. Programming and Computer Software\u00a028, 243\u2013249 (2002)","journal-title":"Programming and Computer Software"},{"issue":"5","key":"23_CR13","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/S0020-0190(02)00511-2","volume":"86","author":"A. Okhotin","year":"2003","unstructured":"Okhotin, A.: The hardest linear conjunctive language. Information Processing Letters\u00a086(5), 247\u2013253 (2003)","journal-title":"Information Processing Letters"},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/3-540-45061-0_21","volume-title":"Automata, Languages and Programming","author":"A. Okhotin","year":"2003","unstructured":"Okhotin, A.: Decision problems for language equations with Boolean operations. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol.\u00a02719, pp. 239\u2013251. Springer, Heidelberg (2003)"},{"issue":"1","key":"23_CR15","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":"23_CR16","doi-asserted-by":"crossref","unstructured":"Okhotin, A.: Recursive descent parsing for Boolean grammars. Acta Informatica (to appear)","DOI":"10.1007\/s00236-007-0045-0"},{"issue":"2-3","key":"23_CR17","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/j.tcs.2005.07.019","volume":"345","author":"A. Okhotin","year":"2005","unstructured":"Okhotin, A.: The dual of concatenation. Theoretical Computer Science\u00a0345(2-3), 425\u2013447 (2005)","journal-title":"Theoretical Computer Science"},{"key":"23_CR18","first-page":"96","volume":"91","author":"A. Okhotin","year":"2007","unstructured":"Okhotin, A.: Nine open problems for conjunctive and Boolean grammars. Bulletin of the EATCS\u00a091, 96\u2013119 (2007)","journal-title":"Bulletin of the EATCS"},{"issue":"2","key":"23_CR19","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(96)00077-1","volume":"168","author":"Y. Rogozhin","year":"1996","unstructured":"Rogozhin, Y.: Small universal Turing machines. Theoretical Computer Science\u00a0168(2), 215\u2013240 (1996)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"23_CR20","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I.H. Sudborough","year":"1975","unstructured":"Sudborough, I.H.: A note on tape-bounded complexity classes and linear context-free languages. Journal of the ACM\u00a022(4), 499\u2013500 (1975)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Machines, Computations, and Universality"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74593-8_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,22]],"date-time":"2021-08-22T04:39:44Z","timestamp":1629607184000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74593-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540745921","9783540745938"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74593-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}