{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T09:58:38Z","timestamp":1773655118112,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540310235","type":"print"},{"value":"9783540330974","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11605157_7","type":"book-chapter","created":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T15:07:40Z","timestamp":1141225660000},"page":"78-89","source":"Crossref","is-referenced-by-count":5,"title":["Prime Normal Form and Equivalence of Simple Grammars"],"prefix":"10.1007","author":[{"given":"C\u00e9dric","family":"Bastien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jurek","family":"Czyzowicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Fraczak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/3-540-51859-2_8","volume-title":"Optimal Algorithms","author":"D. Caucal","year":"1989","unstructured":"Caucal, D.: A fast algorithm to decide on simple grammars equivalence. In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol.\u00a0401, pp. 66\u201385. Springer, Heidelberg (1989)"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: Une forme canonique pour les grammaires simples deterministes. RAIRO informatique, 19\u201336 (1974)","DOI":"10.1051\/ita\/197408R100191"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Korenjak, A.J., Hopcroft, J.E.: Simple deterministic languages. In: Proc. IEEE 7th Annual Symposium on Switching and Automata Theory. IEEE Symposium on Foundations of Computer Science, pp. 36\u201346 (1966)","DOI":"10.1109\/SWAT.1966.22"},{"key":"7_CR4","volume-title":"Introduction to formal language theory","author":"M. Harrison","year":"1978","unstructured":"Harrison, M.: Introduction to formal language theory. Addison-Wesley, Reading (1978)"},{"key":"7_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/0304-3975(95)00064-X","volume":"158","author":"Y. Hirshfeld","year":"1996","unstructured":"Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theoretical Computer Science\u00a0158, 143\u2013159 (1996)","journal-title":"Theoretical Computer Science"},{"key":"7_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Algorithms - ESA \u201994","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol.\u00a0855, pp. 460\u2013470. Springer, Heidelberg (1994)"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-60044-2_44","volume-title":"Combinatorial Pattern Matching","author":"M. Karpinski","year":"1995","unstructured":"Karpinski, M., Rytter, W., Shinohara, A.: Pattern-matching for strings with short descriptions. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, pp. 205\u2013214. Springer, Heidelberg (1995)"},{"key":"7_CR8","first-page":"187","volume":"1","author":"M. Miyazaki","year":"2000","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching for strings in terms of straight-line programs. Journal of Discrete Algorithms\u00a01, 187\u2013204 (2000)","journal-title":"Journal of Discrete Algorithms"},{"key":"7_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-540-30500-2_11","volume-title":"Implementation and Application of Automata","author":"W. Debski","year":"2005","unstructured":"Debski, W., Fraczak, W.: Concatenation state machines and simple functions. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 113\u2013124. Springer, Heidelberg (2005)"},{"key":"7_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/3-540-44977-9_8","volume-title":"Implementation and Application of Automata","author":"J. Czyzowicz","year":"2003","unstructured":"Czyzowicz, J., Fraczak, W., Pelc, A., Rytter, W.: Prime decompositions of regular prefix codes. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol.\u00a02608, pp. 85\u201394. Springer, Heidelberg (2003)"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.ipl.2003.10.006","volume":"89","author":"W. Fraczak","year":"2004","unstructured":"Fraczak, W., Podolak, A.: A characterization of s-languages. Information Processing Letters\u00a089, 65\u201370 (2004)","journal-title":"Information Processing Letters"},{"key":"7_CR12","first-page":"869","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004","author":"L. Georgiadis","year":"2004","unstructured":"Georgiadis, L., Tarjan, R.E.: Finding dominators revisited: extended abstract. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, pp. 869\u2013878. SIAM, Philadelphia (2004)"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/BF01744577","volume":"16","author":"B. Courcelle","year":"1983","unstructured":"Courcelle, B.: An axiomatic approach to the Korenjak-Hopcroft algorithms. Mathematical Systems Theory\u00a016, 191\u2013231 (1983)","journal-title":"Mathematical Systems Theory"},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel\u2013Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Science\u00a0302, 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11605157_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:05:26Z","timestamp":1619507126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11605157_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540310235","9783540330974"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/11605157_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}