{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:14Z","timestamp":1760202614771},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540243182"},{"type":"electronic","value":"9783540305002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-30500-2_7","type":"book-chapter","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T16:39:36Z","timestamp":1267461576000},"page":"68-79","source":"Crossref","is-referenced-by-count":2,"title":["Some Non-semi-decidability Problems for Linear and Deterministic Context-Free Languages"],"prefix":"10.1007","author":[{"given":"Henning","family":"Bordihn","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","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. Journal of the ACM\u00a029, 404\u2013407 (1982)","journal-title":"Journal of the ACM"},{"key":"7_CR2","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"B.S. Baker","year":"1974","unstructured":"Baker, B.S., Book, R.V.: Reversal-bounded multipushdown machines. Journal of Computer and System Sciences\u00a08, 315\u2013332 (1974)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR3","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\u00a014, 143\u2013177 (1961)","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Bordihn, H.: Context-freeness of the power of context-free languages is undecidable. Theoretical Computer Science (2003) (to appear)","DOI":"10.1016\/j.tcs.2003.08.005"},{"key":"7_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/3-540-46011-X_11","volume-title":"Developments in Language Theory","author":"T. Cachat","year":"2002","unstructured":"Cachat, T.: The power of one-letter rational languages. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 145\u2013154. Springer, Heidelberg (2002)"},{"key":"7_CR6","first-page":"341","volume-title":"Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology","author":"H. Calbrix","year":"1996","unstructured":"Calbrix, H., Nivat, M.: Prefix and period languages and rational \u03c9-languages. In: Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology, pp. 341\u2013349. World Scientific, Singapore (1996)"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/321150.321153","volume":"10","author":"S. Ginsburg","year":"1963","unstructured":"Ginsburg, S., Rose, G.F.: Some recursively unsolvable problem in ALGOL-like languages. Journal of the ACM\u00a010, 29\u201347 (1963)","journal-title":"Journal of the ACM"},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"333","DOI":"10.2307\/1994067","volume":"113","author":"S. Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded ALGOL-like languages. Transactions of the American Matematical Society\u00a0113, 333\u2013368 (1964)","journal-title":"Transactions of the American Matematical Society"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/S0019-9958(63)90149-9","volume":"6","author":"S.A. Greibach","year":"1963","unstructured":"Greibach, S.A.: The undecidability of ambiguity problem for minimal linear grammars. Information and Control\u00a06, 117\u2013125 (1963)","journal-title":"Information and Control"},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1145\/321356.321365","volume":"13","author":"S.A. Greibach","year":"1966","unstructured":"Greibach, S.A.: The unsolvability of the recognition of linear context-free languages. Journal of the ACM\u00a013, 582\u2013587 (1966)","journal-title":"Journal of the ACM"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/S0019-9958(64)90422-X","volume":"7","author":"M. Gross","year":"1963","unstructured":"Gross, M.: Inherent ambiguity of minimal linear grammars. Information and Control\u00a07(3), 366\u2013368 (1963)","journal-title":"Information and Control"},{"key":"7_CR12","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. American Mathematical Society, Providence (1967)"},{"key":"7_CR13","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1007\/3-540-45005-X_19","volume-title":"Developments in Language Theory","author":"S. Horv\u00e1th","year":"2003","unstructured":"Horv\u00e1th, S., Leupold, P., Lischke, G.: Roots and powers of regular languages. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol.\u00a02450, pp. 220\u2013230. Springer, Heidelberg (2003)"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R.: Parenthesis grammars. Journal of the ACM\u00a014, 490\u2013500 (1967)","journal-title":"Journal of the ACM"},{"key":"7_CR16","series-title":"ACM Monograph Series","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"Salomaa, A.: Formal Languages. ACM Monograph Series. Academic Press, London (1973)"},{"key":"7_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2003","unstructured":"S\u00e9nizergues, G.: L(A)=L(B)? Decidability results from complete formal systems. Theoretical Computer Science\u00a0251, 1\u2013166 (2003)","journal-title":"Theoretical Computer Science"},{"key":"7_CR18","volume-title":"Theory of Computation","author":"D. Wood","year":"1987","unstructured":"Wood, D.: Theory of Computation. John Wiley & Sons, Chichester (1987)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30500-2_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:57:22Z","timestamp":1605761842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30500-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540243182","9783540305002"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30500-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}