{"entities":{"Q689634":{"pageid":691483,"ns":120,"title":"Item:Q689634","lastrevid":63505179,"modified":"2026-04-11T13:36:58Z","type":"item","id":"Q689634","labels":{"en":{"language":"en","value":"Constructor equivalent term rewriting systems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 446244"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$655163EB-1B9A-431F-B8E4-94A73B416E7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c2d37320bf16f0e7bbf7efa5d8e3ed87bf748cbb","datavalue":{"value":{"text":"Constructor equivalent term rewriting systems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q689634$615753BF-83E2-43EC-BB4F-012AD1F76F40","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"90dd35e7bbf5640c1a76cdc9d45cedf09a6aca7e","datavalue":{"value":"0780.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689634$8AD2A889-55EA-4D6D-A4F5-24B91A6A612A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f96a979ecd4261537a59d8d66e1cc9c8cbdb56fb","datavalue":{"value":"10.1016/0020-0190(93)90236-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689634$E0451A35-8C94-4201-A038-3596643C5FEF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b360dc0f9cdfe65809a8fb545e8df79a2952addb","datavalue":{"value":{"entity-type":"item","numeric-id":674752,"id":"Q674752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$4E313F2C-ADBF-4E22-83D7-F1752B61CB0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c53283f06a783eebebf881549b5dd1ed498267f","datavalue":{"value":{"entity-type":"item","numeric-id":248923,"id":"Q248923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$9523FA85-D721-4086-B412-D4209069B58C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$3512790D-B6ED-445F-87BE-ED3897F131B5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7a041ac255fcd8e6d725677dd2f4aa6770323c3e","datavalue":{"value":{"time":"+1993-11-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q689634$A0581F1F-A84F-41F7-AE88-56F6184ED96D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f10ca524c079c5f55da3bb0e930f1f84d40182a0","datavalue":{"value":"We restrict ourselves to the class of orthogonal term rewriting systems (formerly called regular systems). The class of strongly sequential term rewriting systems (SS) was defined by \\textit{Huet} and \\textit{L\u00e9vy}. Strongly sequential systems admit an efficient one-step reduction strategy; strong sequentiality is decidable but is conjectured to be NP- complete. The class of forward-branchingsystems (FB) is a subclass of \\(SS\\); forward-branching systems admit an efficient strategy for seuqences of reductions; the forward-branching property can be decided in polynomial time.   \\textit{Thatte} demonstrated the possibility of simulating an orthogonal \\(TRS\\) with a left-linear constructor system obtained from the original system via a simple transformation. With examples, we point out that Thatte's transformation does not always preserve orthogonality and that if it does, it does not always preserve strong sequentiality. This leads us to define a new subclass of \\(SS\\): the class of constructor equivalent systems (\\(CE\\)) for which Thatte's transformation preserves strong sequentiality. We give a simple characterization of \\(CE\\) and show that it is a subclass of \\(FB\\). This work motivates our choice of studying nonconstructor systems linke \\(FB\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q689634$A3B7B679-930A-4C14-A044-B7AA934747D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689634$96A8D94A-876C-41AD-A5D0-8259A23B9D55","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"44f4de845265594946c805aa62c8ae56e3a4e3f4","datavalue":{"value":"446244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689634$C5F46F5D-B411-493A-9FF9-E45EA12BFB9E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac208301aacad3534f2348fb14e6fb3baf3da3db","datavalue":{"value":"equational programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q689634$FA63286A-89B1-463F-8FEE-0161CD03622D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73766346b2fa658a700a327720fd7d9a004c6a4f","datavalue":{"value":"constructor system","type":"string"},"datatype":"string"},"type":"statement","id":"Q689634$63F771A3-E291-4737-B64C-6B650C56577C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$3D6F353F-9746-4B81-BB4E-EBF1713E626F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70526d4926da27f8641c0b8ed113784d2d9747c7","datavalue":{"value":"https://doi.org/10.1016/0020-0190(93)90236-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q689634$FF6BC85E-BA6D-4B1B-9A4B-010BF8CFF4AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"10aa2cbbf60eca942454387e15323c7c451ec8a0","datavalue":{"value":"W2010129996","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q689634$CBAFFE28-B7F2-4168-890E-FBA4241AF9E3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"621c74ec4ffc782a3586c027189f19d5c2ee9673","datavalue":{"value":{"entity-type":"item","numeric-id":1892142,"id":"Q1892142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$4653FD0D-46E1-4073-A268-2523D95FC467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbd234d88ae98f8bbeb427a6347d67c58414dd07","datavalue":{"value":{"entity-type":"item","numeric-id":1338780,"id":"Q1338780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$3FF895DE-64B6-4C7C-B096-3F584EE0521F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c527e263525faa34ac4a72501bf8563b41ad015a","datavalue":{"value":{"entity-type":"item","numeric-id":4297316,"id":"Q4297316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$8521E470-E14F-4E53-B73F-835A704D6F8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a1de7a41a5c09d0b7d2c0b459018288964db062","datavalue":{"value":{"entity-type":"item","numeric-id":3805891,"id":"Q3805891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$572FC953-3049-439D-8491-F628AF239803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5147416ec2161493d5545370272bdd687c6708c","datavalue":{"value":{"entity-type":"item","numeric-id":1186735,"id":"Q1186735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$E0317851-D2BA-4347-B2AA-B63E766DAF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bccdf7173fbc3e3fcf1b15214f83d5bbcd461200","datavalue":{"value":{"entity-type":"item","numeric-id":5055738,"id":"Q5055738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$7F02CE42-BF43-4243-ACA5-3541E12CB512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"016e8963cc34ca4f74cab0dbda793d95e86a5221","datavalue":{"value":{"entity-type":"item","numeric-id":1059392,"id":"Q1059392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$272A65FF-51FC-4CB7-8FC1-9BD8493C587E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d512bf90ee6db3a4baa20c6eec43f385f28cf6a","datavalue":{"value":{"entity-type":"item","numeric-id":1093366,"id":"Q1093366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q689634$8744648B-954C-4171-9BD2-E50EB0C874FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24699d25f0c6d812b1a4a1f877e2340c52be9010","datavalue":{"value":{"entity-type":"item","numeric-id":1338780,"id":"Q1338780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4efad99edf6bf472831df2daeaa4f639d9d6b057","datavalue":{"value":{"amount":"+0.9043181538581848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689634$816C0C7E-8A98-4488-A743-D741C27804FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81f4d893081f0a342c302224ba339edd0f5ac089","datavalue":{"value":{"entity-type":"item","numeric-id":1093366,"id":"Q1093366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4efad99edf6bf472831df2daeaa4f639d9d6b057","datavalue":{"value":{"amount":"+0.9043181538581848","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689634$7789C384-AA40-4B83-B1D6-71E171273645","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"946df74ccf4dc68559e50e2ab772e69aec18121c","datavalue":{"value":{"entity-type":"item","numeric-id":674754,"id":"Q674754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdbe475b0a23dbc3fc570c3af9c81684cde4ecc3","datavalue":{"value":{"amount":"+0.8319866061210632","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689634$9106F538-4B1B-42BB-9791-88FEB768339D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b7c02d8b408b8e4e670f4311aad9e6588764b9f","datavalue":{"value":{"entity-type":"item","numeric-id":1029079,"id":"Q1029079"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e34c23d89e9351139e083bb8987b315450e14df","datavalue":{"value":{"amount":"+0.8319863677024841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689634$BBCF2ADF-7931-4228-B887-409B1E8797CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe30c8774e60656e8437641d0e0f789562e6f9f9","datavalue":{"value":{"entity-type":"item","numeric-id":1059392,"id":"Q1059392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e910a9c921ad3d508726ec0f6991f90afaf16f93","datavalue":{"value":{"amount":"+0.7891107797622681","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q689634$82068D59-6A05-477C-8D25-767E3320EEDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Constructor equivalent term rewriting systems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Constructor_equivalent_term_rewriting_systems"}}}}}