{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T08:59:35Z","timestamp":1754557175806},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540628446"},{"type":"electronic","value":"9783540687030"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-62844-4_2","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:50:45Z","timestamp":1330278645000},"page":"10-26","source":"Crossref","is-referenced-by-count":7,"title":["Conditional context-free languages of finite index"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0019-9958(65)90196-8","volume":"8","author":"E. Altman","year":"1965","unstructured":"E. Altman and R. Banerji. Some problems of finite representability. Inf. Contr., 8:251\u2013263, 1965.","journal-title":"Inf. Contr."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity Theory I. Springer, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/S0019-9958(63)90199-2","volume":"6","author":"R. B. Banerji","year":"1963","unstructured":"R. B. Banerji. Phrase structure languages, finite machines, and channel capacity. Inf. Contr., 6:153\u2013162, 1963.","journal-title":"Inf. Contr."},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0019-9958(79)90642-9","volume":"43","author":"J. Beauquier","year":"1979","unstructured":"J. Beauquier. Deux familles de langages incomparables. Inf. Contr., 43:101\u2013122, 1979.","journal-title":"Inf. Contr."},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1016\/S0019-9958(67)90771-1","volume":"11","author":"B. Brainerd","year":"1968","unstructured":"B. Brainerd. An analog of a theorem about context-free languages. Inf. Contr., 11:561\u2013567, 1968.","journal-title":"Inf. Contr."},{"key":"2_CR6","volume-title":"Grammar Systems: A Grammatical Approach to Distribution and Cooperation","author":"E. Csuhaj-Varj\u00fa","year":"1994","unstructured":"E. Csuhaj-Varj\u00fa, J. Dassow, J. Kelemen, and Gh. P\u0103un. Grammar Systems: A Grammatical Approach to Distribution and Cooperation. London: Gordon and Breach, 1994."},{"key":"2_CR7","first-page":"71","volume-title":"2nd International Colloquium on Words, Languages, and Combinatorics","author":"J. Dassow","year":"1990","unstructured":"J. Dassow and H. Hornig. Conditional grammars with subregular conditions. In 2nd International Colloquium on Words, Languages, and Combinatorics, pages 71\u201386. Kyoto Sangyo Unversity (Japan), World Scientific, August 1990."},{"key":"2_CR8","volume-title":"volume 18 of EATCS Monographs in Theoretical Computer Science","author":"J. Dassow","year":"1989","unstructured":"J. Dassow and Gh. P\u0103un. Regulated Rewriting in Formal Language Theory, volume 18 of EATCS Monographs in Theoretical Computer Science. Berlin: Springer, 1989."},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0020-0190(95)00008-Z","volume":"54","author":"G. Dong","year":"1995","unstructured":"G. Dong. On the index of positive programmed formal languages. IPL, 54:105\u2013110, 1995.","journal-title":"IPL"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"D. Ferment. Principality results about some matrix language families. In J. Paredaens, editor, 11th ICALP'84, volume 172 of LNCS, pages 151\u2013161, 1984.","DOI":"10.1007\/3-540-13345-3_14"},{"key":"2_CR11","volume-title":"Technical Report TR 185-2\/FR-1\/96","author":"H. Fernau","year":"1996","unstructured":"H. Fernau, R. Freund, and M. Holzer. External versus internal hybridization for cooperating distributed grammar systems. Technical Report TR 185-2\/FR-1\/96, Technische Universit\u00e4t Wien (Austria), 1996."},{"key":"2_CR12","volume-title":"Technical Report WSI-96-16","author":"H. Fernau","year":"1996","unstructured":"H. Fernau and M. Holzer. Regulated finite index language families collapse. Technical Report WSI-96-16, Universit\u00e4t T\u00fcbingen (Germany), Wilhelm-Schickard-Institut f\u00fcr Informatik, 1996."},{"issue":"3","key":"2_CR13","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1137\/0304034","volume":"4","author":"S. Ginsburg","year":"1966","unstructured":"S. Ginsburg and E. H. Spanier. Finite-turn pushdown automata. SIAM Journal of Control, 4(3):429\u2013453, 1966.","journal-title":"SIAM Journal of Control"},{"key":"2_CR14","first-page":"228","volume":"2","author":"S. Ginsburg","year":"1968","unstructured":"S. Ginsburg and E. H. Spanier. Derivation-bounded languages. JCSS, 2:228\u2013250, 1968.","journal-title":"JCSS"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1016\/S0019-9958(71)90095-7","volume":"19","author":"J. Gruska","year":"1971","unstructured":"J. Gruska. A few remarks on the index of context-free grammars and languages. Inf. Contr., 19:216\u2013223, 1971.","journal-title":"Inf. Contr."},{"key":"2_CR16","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1007\/BF01178731","volume":"31","author":"D. Hauschildt","year":"1994","unstructured":"D. Hauschildt and M. Jantzen. Petri net algorithms in the theory of matrix grammars. Acta Informatica, 31:719\u2013728, 1994.","journal-title":"Acta Informatica"},{"issue":"5","key":"2_CR17","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal Comput., 17(5):935\u2013938, 1988.","journal-title":"SIAM Journal Comput."},{"key":"2_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N. D. Jones","year":"1977","unstructured":"N. D. Jones and W. T. Laaser. Complete problems for deterministic polynomial time. TCS, 3:105\u2013117, 1977.","journal-title":"TCS"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"D. Kozen. Lower bounds for natural proof systems. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, pages 254\u2013266, 1977.","DOI":"10.1109\/SFCS.1977.16"},{"key":"2_CR20","first-page":"327","volume-title":"The Book of L","author":"M. Latteux","year":"1985","unstructured":"M. Latteux and A. Terlutte. The Parikh-boundedness of ET0L languages of finite index. In G. Rozenberg and A. K. Salomaa, editors, The Book of L, pages 327\u2013338. Berlin: Springer, 1985."},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/S0019-9958(77)90163-2","volume":"35","author":"G. P\u0103un","year":"1977","unstructured":"Gh. P\u0103un. On the index of grammars and languages. Inf. Contr., 35:259\u2013266, 1977.","journal-title":"Inf. Contr."},{"issue":"3","key":"2_CR22","first-page":"267","volume":"18","author":"G. P\u0103un","year":"1979","unstructured":"Gh. P\u0103un. On the family of finite index matrix languages. JCSS, 18(3):267\u2013280, 1979.","journal-title":"JCSS"},{"key":"2_CR23","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1016\/S0019-9958(79)90664-8","volume":"43","author":"G. P\u0103un","year":"1979","unstructured":"Gh. P\u0103un. On the generative capacity of conditional grammars. Inf. Contr., 43:178\u2013186, 1979.","journal-title":"Inf. Contr."},{"issue":"1","key":"2_CR24","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1051\/ita\/1980140101191","volume":"14","author":"G. P\u0103un","year":"1980","unstructured":"Gh. P\u0103un. Some consequences of a result of Ehrenfeucht and Rozenberg. RAIRO Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications, 14(1):119\u2013122, 1980.","journal-title":"RAIRO Informatique th\u00e9orique et Applications\/Theoretical Informatics and Applications"},{"issue":"5","key":"2_CR25","first-page":"391","volume":"XXVIII","author":"G. P\u0103un","year":"1983","unstructured":"Gh. P\u0103un. Length-increasing grammars of finite index. Rev. Roumaine Math. Pures Appl., XXVIII(5):391\u2013403, 1983.","journal-title":"Rev. Roumaine Math. Pures Appl."},{"issue":"1","key":"2_CR26","first-page":"83","volume":"27","author":"G. P\u0103un","year":"1983","unstructured":"Gh. P\u0103un. Some context-free-like properties of finite index matrix languages. Bull. Math. de la Soc. Sci. Math. de Roumanie, 27(1):83\u201387, 1983.","journal-title":"Bull. Math. de la Soc. Sci. Math. de Roumanie"},{"key":"2_CR27","first-page":"324","volume":"6","author":"V. Rajlich","year":"1972","unstructured":"V. Rajlich. Absolutely parallel grammars and two-way deterministic finite state transducers. JCSS, 6:324\u2013342, 1972.","journal-title":"JCSS"},{"issue":"4","key":"2_CR28","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/0020-0190(76)90004-1","volume":"5","author":"G. Rozenberg","year":"1976","unstructured":"G. Rozenberg. More on ET0L systems versus random context grammars. IPL, 5(4):102\u2013106, 1976.","journal-title":"IPL"},{"key":"2_CR29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0019-9958(78)90050-5","volume":"38","author":"G. Rozenberg","year":"1978","unstructured":"G. Rozenberg and D. Vermeir. On ET0L systems of finite index. Inf. Contr., 38:103\u2013133, 1978.","journal-title":"Inf. Contr."},{"key":"2_CR30","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/S0019-9958(78)90635-6","volume":"39","author":"G. Rozenberg","year":"1978","unstructured":"G. Rozenberg and D. Vermeir. On the effect of the finite index restriction on several families of grammars. Inf. Contr., 39:284\u2013302, 1978.","journal-title":"Inf. Contr."},{"issue":"3","key":"2_CR31","first-page":"126","volume":"3","author":"G. Rozenberg","year":"1978","unstructured":"G. Rozenberg and D. Vermeir. On the effect of the finite index restriction on several families of grammars; Part 2: context dependent systems and grammars. Foundations of Control Engineering, 3(3):126\u2013142, 1978.","journal-title":"Foundations of Control Engineering"},{"key":"2_CR32","series-title":"volume 71 of LNCS","first-page":"479","volume-title":"Extending the notion of finite index","author":"G. Rozenberg","year":"1979","unstructured":"G. Rozenberg and D. Vermeir. Extending the notion of finite index. In H. A. Maurer, editor, Colloquium on Automata, Languages and Programming (6), volume 71 of LNCS, pages 479\u2013488. Berlin: Springer, July 1979."},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1016\/0890-5401(87)90012-5","volume":"74","author":"B. Rozoy","year":"1987","unstructured":"B. Rozoy. The Dyck language D\u20321 is not generated by any matrix grammar of finite index. Inf. Comp., 74:64\u201389, 1987.","journal-title":"Inf. Comp."},{"key":"2_CR34","first-page":"216","volume":"28","author":"W. L. Ruzzo","year":"1984","unstructured":"W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. JCSS, 28:216\u2013230, 1984.","journal-title":"JCSS"},{"key":"2_CR35","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1016\/S0019-9958(69)90164-8","volume":"14","author":"A. K. Salomaa","year":"1969","unstructured":"A. K. Salomaa. On the index of a context-free grammar and language. Inf. Contr., 14:474\u2013477, 1969.","journal-title":"Inf. Contr."},{"key":"2_CR36","unstructured":"A. K. Salomaa. Formal Languages. Academic Press, 1973."},{"key":"2_CR37","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C. E. Shannon","year":"1948","unstructured":"C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:379\u2013423, 1948.","journal-title":"The Bell System Technical Journal"},{"issue":"1","key":"2_CR38","first-page":"87","volume":"VII","author":"E. D. Stotskii","year":"1971","unstructured":"E. D. Stotskii. Formal grammars and limitations for derivations. Problemy peredacii informacii (in Russ.), VII(1):87\u2013101, 1971.","journal-title":"Problemy peredacii informacii (in Russ.)"},{"issue":"4","key":"2_CR39","first-page":"40","volume":"2","author":"E. D. Stotskii","year":"1972","unstructured":"E. D. Stotskii. On some strict hierarchies of languages. Naucno-tehniceskaya informaciya, Seriya 2 (in Russ), (4):40\u201345, 1972.","journal-title":"Naucno-tehniceskaya informaciya, Seriya"},{"issue":"4","key":"2_CR40","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/321906.321913","volume":"22","author":"I. H. Sudborough","year":"1975","unstructured":"I. H. Sudborough. A note on tape-bounded complexity classes and linear context-free languages. JACM, 22(4):499\u2013500, October 1975.","journal-title":"JACM"},{"key":"2_CR41","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. JACM, 25:405\u2013414, 1978.","journal-title":"JACM"},{"key":"2_CR42","first-page":"96","volume":"33","author":"R. Szelepcs\u00e9nyi","year":"1987","unstructured":"R. Szelepcs\u00e9nyi. The method of forcing for nondeterministic automata. EATCS Bull., 33:96\u2013100, October 1987.","journal-title":"EATCS Bull."},{"key":"2_CR43","first-page":"341","volume":"28","author":"F. J. Urbanek","year":"1983","unstructured":"F. J. Urbanek. A note on conditional grammars. Rev. Roumaine Math. Pures Appl., 28:341\u2013342, 1983.","journal-title":"Rev. Roumaine Math. Pures Appl."},{"issue":"5","key":"2_CR44","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/0020-0190(75)90027-7","volume":"3","author":"J. Leeuwen van","year":"1975","unstructured":"J. van Leeuwen. The membership problem for ET0L-languages is polynomially complete. IPL, 3(5):138\u2013143, May 1975.","journal-title":"IPL"}],"container-title":["Lecture Notes in Computer Science","New Trends in Formal Languages"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-62844-4_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:14:21Z","timestamp":1605629661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-62844-4_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540628446","9783540687030"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/3-540-62844-4_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}