{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:12:13Z","timestamp":1725664333055},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540592006"},{"type":"electronic","value":"9783540492238"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59200-8_57","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:05:39Z","timestamp":1330275939000},"page":"194-209","source":"Crossref","is-referenced-by-count":0,"title":["A polynomial algorithm testing partial confluence of basic semi-Thue systems"],"prefix":"10.1007","author":[{"given":"G\u00e9raud","family":"S\u00e9nizergues","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"S. Arnborg, B. Courcelle, A. Proskurowski, and D. Seese. An algebraic theory of graph reduction. J. ACM 40, pages 1134\u20131164, 1993.","journal-title":"J. ACM"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/BF01368784","volume":"25","author":"J.M. Autebert","year":"1992","unstructured":"J.M. Autebert and L. Boasson. The equivalence of pre-NTS grammars is decidable. Math.Systems Theory 25, pages 61\u201374, 1992.","journal-title":"Math.Systems Theory"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"J. Berstel and L. Boasson. Context-free languages. In Handbook of theoretical computer science, vol.B, Chapter 2, pages 59\u2013102. Elsevier, 1991.","DOI":"10.1016\/B978-0-444-88074-1.50007-X"},{"key":"16_CR4","unstructured":"L. Boasson. Grammaires \u00e0 non-terminaux s\u00e9par\u00e9s. In Proceedings 7th ICALP, pages 105\u2013118. LNCS 85, 1980."},{"issue":"nr3","key":"16_CR5","first-page":"332","volume":"31","author":"L. Boasson","year":"1985","unstructured":"L. Boasson and G. S\u00e9nizergues. NTS languages are deterministic and congruential. JCSS 31, nr 3, pages 332\u2013342, 1985.","journal-title":"JCSS"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(82)90036-6","volume":"19","author":"R.V. Book","year":"1982","unstructured":"R.V. Book, M. Jantzen, and C. Wrathall. Monadic Thue systems. TCS 19, pages 231\u2013251, 1982.","journal-title":"TCS"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"R.V. Book and F. Otto. String Rewriting Systems. Texts and monographs in Computer Science. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"16_CR8","unstructured":"H. B\u00fccken. Reduction systems and small cancellation theory. In Proceedings 4th Workshop on Automated Deduction, pages 53\u201359, 1979."},{"key":"16_CR9","unstructured":"P. Butzbach. Sur l'\u00e9quivalence des grammaires simples. In Actes des Premi\u00e8res journ\u00e9es d'Informatique Th\u00e9orique, Bonascre. ENSTA, 1973."},{"key":"16_CR10","unstructured":"P. Butzbach. Une famille de congruences de Thue pour lesquelles l'\u00e9quivalence est d\u00e9cidable. In Proceedings 1rst ICALP, pages 3\u201312. LNCS, 1973."},{"key":"16_CR11","unstructured":"P. Le Chenadec. Canonical Forms in Finitely Presented Algebras. Research Notes in Theoretical Computer Science, Pitman Wiley & sons, 1986."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"L. Chottin. Strict deterministic languages and controlled rewriting systems. In Proceedings 6th ICALP, pages 104\u2013117. LNCS 71, Springer-Verlag, 1979.","DOI":"10.1007\/3-540-09510-1_9"},{"key":"16_CR13","unstructured":"Y. Cochet. Sur l'alg\u00e9bricit\u00e9 des classes de certaines congruences d\u00e9finies sur le monoide libre. Th\u00e8se de l'universit\u00e9 de Rennes, 1971."},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"N. Dershowitz and J.P. Jouannaud. Rewrite systems. In Handbook of theoretical computer science, vol.B, Chapter 2, pages 243\u2013320. Elsevier, 1991.","DOI":"10.1016\/B978-0-444-88074-1.50011-1"},{"key":"16_CR15","unstructured":"J. Engelfriet. Deciding the NTS-property of context-free grammars. Tech. report 94-05, Leiden university, pages 1\u20137, 1994. To appear in the proceedings of the conference on Important Results and Trends in Theoretical Computer Science, Graz, Austria, June 1994."},{"issue":"No1","key":"16_CR16","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1137\/0211013","volume":"11","author":"E.P. Friedman","year":"1982","unstructured":"E.P. Friedman and S.A. Greibach. A polynomial algorithm for deciding the equivalence problem for 2-tape deterministic finite state acceptors. SIAM J. COMPUT., vol. 11, No 1, pages 166\u2013183, 1982.","journal-title":"SIAM J. COMPUT."},{"issue":"No3","key":"16_CR17","doi-asserted-by":"publisher","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. J. SIAM Control, vol. 4, No 3, pages 429\u2013453, 1966.","journal-title":"J. SIAM Control"},{"key":"16_CR18","unstructured":"P. Grosset-Grange. D\u00e9cidabilit\u00e9 de la confluence partielle d'un syst\u00e8me semi-Thu\u00e9ien rationnel. Memoire de DEA de l'universit\u00e9 de Bordeaux 1, pages 1\u201321, 1993."},{"key":"16_CR19","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1016\/0304-3975(91)90356-7","volume":"78","author":"T. Harju","year":"1991","unstructured":"T. Harju and J. Karhum\u00e4ki. The equivalence problem of multitape finite automata. TCS 78, pages 347\u2013355, 1991.","journal-title":"TCS"},{"issue":"no4","key":"16_CR20","doi-asserted-by":"publisher","first-page":"797","DOI":"10.1145\/322217.322230","volume":"27","author":"G. Huet","year":"1980","unstructured":"G. Huet. Confluent reductions:abstract properties and applications to term rewriting systems. JACM vol. 27 no 4, pages 797\u2013821, 1980.","journal-title":"JACM"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"K. Madlener, P. Narendran, and F. Otto. A specialized completion procedure for monadic string-rewriting systems presenting groups. In Proceedings 18th ICALP, pages 279\u2013290. Springer, LNCS No 510, 1991.","DOI":"10.1007\/3-540-54233-7_141"},{"key":"16_CR22","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0304-3975(93)90213-D","volume":"113","author":"K. Madlener","year":"1993","unstructured":"K. Madlener, P. Narendran, F. Otto, and L. Zhang. On weakly confluent monadic string-rewriting systems. TCS 113, pages 119\u2013165, 1993.","journal-title":"TCS"},{"key":"16_CR23","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BF02090778","volume":"23","author":"P. Narendran","year":"1990","unstructured":"P. Narendran. It is decidable whether a monadic Thue system is canonical over a regular set. Math. Systems Theory 23, pages 245\u2013254, 1990.","journal-title":"Math. Systems Theory"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"M. Nivat. On some families of languages related to the Dyck language. 2nd Annual Symposium on Theory of Computing, 1970.","DOI":"10.1145\/800161.805168"},{"key":"16_CR25","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0304-3975(83)90060-9","volume":"2","author":"C. O'Dunlaing","year":"1983","unstructured":"C. O'Dunlaing. Infinite regular Thue systems. TCS 2, pages 171\u2013192, 1983.","journal-title":"TCS"},{"key":"16_CR26","first-page":"285","volume":"35","author":"F. Otto","year":"1987","unstructured":"F. Otto. On deciding the confluence of a finite string-rewriting system on a given congruence class. JCSS 35, pages 285\u2013310, 1987.","journal-title":"JCSS"},{"key":"16_CR27","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/BF01213858","volume":"25","author":"F. Otto","year":"1992","unstructured":"F. Otto. The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems. Math. Systems Theory 25, pages 241\u2013251, 1992.","journal-title":"Math. Systems Theory"},{"key":"16_CR28","unstructured":"J. Sakarovitch. Syntaxe des langages de Chomsky, essai sur le d\u00e9terminisme. Th\u00e8se de doctorat d'\u00e9tat de l'universit\u00e9 Paris VII, pages 1\u2013175, 1979."},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"G. S\u00e9nizergues. The equivalence problem for NTS languages is decidable. In Proceedings 6th G.I. Symposium on Theoretical Computer Science, pages 313\u2013323. LNCS Springer-Verlag, nr 145, 1982.","DOI":"10.1007\/BFb0036491"},{"issue":"3","key":"16_CR30","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/0022-0000(85)90055-8","volume":"31","author":"G. S\u00e9nizergues","year":"1985","unstructured":"G. S\u00e9nizergues. The equivalence and inclusion problems for NTS languages. J. Comput. System Sci. 31(3), pages 303\u2013331, 1985.","journal-title":"J. Comput. System Sci."},{"key":"16_CR31","unstructured":"G. S\u00e9nizergues. Sur la description des langages alg\u00e9briques deterministes par des syst\u00e8mes de r\u00e9\u00e9criture confluents. Th\u00e8se d'\u00e9tat, universit\u00e9 Paris 7 et rapport LITP 88-39, pages 1\u2013330, 1987."},{"issue":"3","key":"16_CR32","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0890-5401(89)90032-1","volume":"81","author":"G. S\u00e9nizergues","year":"1989","unstructured":"G. S\u00e9nizergues. Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages. Information and Computation 81(3), pages 265\u2013279, 1989.","journal-title":"Information and Computation"},{"issue":"2","key":"16_CR33","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/0304-3975(90)90123-Y","volume":"70","author":"G. S\u00e9nizergues","year":"1990","unstructured":"G. S\u00e9nizergues. A characterisation of deterministic context-free languages by means of right-congruences. TCS 70 (2), pages 213\u2013232, 1990.","journal-title":"TCS"},{"key":"16_CR34","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0304-3975(90)90048-M","volume":"71","author":"G. S\u00e9nizergues","year":"1990","unstructured":"G. S\u00e9nizergues. Some decision problems about controlled rewriting systems. TCS 71, pages 281\u2013346, 1990.","journal-title":"TCS"},{"key":"16_CR35","unstructured":"L. Zhang. Weak confluence is tractable for finite string-rewriting systems, preprint, pages 1\u201310, 1991."}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59200-8_57.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:59Z","timestamp":1605648359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59200-8_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540592006","9783540492238"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-59200-8_57","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}