{"entities":{"Q2266586":{"pageid":2277329,"ns":120,"title":"Item:Q2266586","lastrevid":78389696,"modified":"2026-05-06T11:28:38Z","type":"item","id":"Q2266586","labels":{"en":{"language":"en","value":"Cancellation rules and extended word problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3894468"}},"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":"Q2266586$E9553728-4A08-4331-819B-9DBB33F784F6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4c6b0fcb54b5e6a9a10dd37723dd0b698d7d85f","datavalue":{"value":{"text":"Cancellation rules and extended word problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2266586$F883259E-0F02-4DA0-893C-62E8D08433F1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6b90b9b1a8d0721b7edd845da1f741b214f6bda1","datavalue":{"value":"0561.68030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$14D26C34-C7C1-41DB-B572-0DF5774F52D1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"714f0ca5ba41ffde771768e1d80fb07b83dd1f30","datavalue":{"value":"10.1016/0020-0190(85)90122-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$4995D933-7A05-46D9-A2DD-6B2ED11DFDCC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ab539a58a8a767731665253837c1bc29c4d22a7e","datavalue":{"value":{"entity-type":"item","numeric-id":593774,"id":"Q593774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$2551E7D2-5C07-4642-A42D-984A9C99E1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f46c7c00558d7121734d489049799fa24953dd04","datavalue":{"value":{"entity-type":"item","numeric-id":287428,"id":"Q287428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$181AFA47-7F9A-4DB6-8A29-EF96D38E21BB","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":"Q2266586$63A1916B-29A6-4B53-8D32-3B9B7F8A6008","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2266586$8B1E5CAF-39F3-4C93-A0EE-DE0DD41BDC27","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"924b42101504e63393138debc2d4afd4a77d8f22","datavalue":{"value":"\\textit{D. Dolev} and \\textit{A. C. Yao} [IEEE Trans. Inf. Theory IT-29, 198- 208 (1983; Zbl 0502.94005)] developed formal models of two-party protocols. Here the sets of cancellation rules underlying their models are shown to be finite homogeneous Thue systems of degree 2 that are Church-Rosser. Now the question of whether or not a given protocol is secure in the sense of Dolev and Yao can be stated as a special case of the following extended word problem: Instance: Two regular sets R and F on \\(\\Sigma\\). Question: Does there exist \\(\\alpha\\in R\\) and \\(\\beta\\in F\\) such that \\(\\alpha\\) is reducible to \\(\\beta\\) ?    Conceptually simple polynomial-time algorithms are given for the above problem and for the following decision problem: Instance: Two regular sets R and F on \\(\\Sigma\\). Question: Does there exist \\(\\alpha\\in R\\) and \\(\\beta\\in F\\) such that \\(\\alpha\\) is congruent to \\(\\beta\\) ?    These algorithms are based on a construction that given a nondeterministic finite state acceptor A with m states yields in \\(O(m^ 4)\\) steps a nondeterministic finite state acceptor with m states, that recognizes the set of descendants of L(A) modulo a given finite homogeneous Thue system of degree 2. All these results can be extended to finite monadic Thue systems, however, the complexity bounds then depend on the maximum length of the left-hand sides of the rules of the Thue system under consideration.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$C6AE90F4-5D1A-4ECA-A828-F7F5C1E8EE76","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$372ABEC5-CFA4-41C7-96D5-596E59A4C67D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$F34063B0-54F4-4986-B01E-389D48036A99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4f2f7daca59c9a2871b70b792569b5d7d486af72","datavalue":{"value":"94A99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$B84ACB89-666B-4F0E-9FE4-3E26D9880AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$DCA78BEC-2C95-4DD9-9F87-F6A830BDFE0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$F47A55D6-3780-448C-BB60-F685AA419522","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"532272b0218c1d719c8f160d841623591a175cb0","datavalue":{"value":"3894468","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2266586$73A04881-2171-4B16-83AD-D3BFF5E3E540","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b14cd685c98a4ba07bb03380be5fdb0df906771e","datavalue":{"value":"congruences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$B3F24929-1EEB-4A21-AAB8-8ECC24D275BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64eaf746f8323aca7f8e059d49fc382a5ad50bde","datavalue":{"value":"Church-Rosser property","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$9A29338F-D37D-4D7A-93F8-56824C9F51E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84c612e97d0bbc5f0fc0c1fc6c648d85c6d9bbe2","datavalue":{"value":"security","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$1C3359B1-C849-4187-89EA-7FA22CFF487D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88c684583d5037b5e8f04d19ea06553eb7e4297d","datavalue":{"value":"two-party protocols","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$8AB81C31-AE9C-4038-93F5-858717FFA813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a115300b75d53df3f1db5b0f1bc5e2a1d6a726f","datavalue":{"value":"cancellation rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$F3867963-1BD4-4827-A903-898D033FB940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"872431b5dc755bcd5b7213492e1cb5e11885541c","datavalue":{"value":"Thue systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$130DB9A4-0CA5-4B34-AFB0-BED12E913313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8853afb2fbe60960e72efdf833c3828b5e149b2d","datavalue":{"value":"extended word problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$7085A087-72D1-423E-B3C2-D176094D06EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a92166f5adeebffc8c81c6abb980ed495030be8","datavalue":{"value":"polynomial-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$F5A70C1E-B578-44A2-92F5-7374DF6C88B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c903ed85bd3f62eafc4372b37884925c9447cb7d","datavalue":{"value":"nondeterministic finite state acceptor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2266586$F4906417-F250-409E-AAEE-AC7E65A34F37","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":"Q2266586$5657053C-2CC8-44E5-AC0F-301C840A78B5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"09eeb53a57e3a236ec25f8fdd27770ac54074dcb","datavalue":{"value":{"entity-type":"item","numeric-id":593775,"id":"Q593775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$47A0F53F-5471-4C93-8CE3-7DEBE1FC42F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84a5beb4ffbe4d8447ef8b9d68fdfb1a8b24a65e","datavalue":{"value":{"entity-type":"item","numeric-id":3677188,"id":"Q3677188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$561BC8B6-9EAD-49C6-92CD-E1799C49F2B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e93f3c3eb08a198e5f96969567b686a9be61b15d","datavalue":{"value":{"entity-type":"item","numeric-id":798317,"id":"Q798317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$8E7499EA-F3CA-4E53-BDD6-EA9AC2B4825E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"937911e42f68d251c82fa9be54759bda8aea4ecb","datavalue":{"value":{"entity-type":"item","numeric-id":1165842,"id":"Q1165842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$D997CBAA-942C-4E14-98D1-5DAEF9799DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3944d11f57df22916bf6d751f60919e8d5446f58","datavalue":{"value":{"entity-type":"item","numeric-id":3323837,"id":"Q3323837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$33880F06-94D6-4086-94E0-937765856C6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a73265bad6ea50fe9fad5bfba6b38941e6752f","datavalue":{"value":{"entity-type":"item","numeric-id":3968876,"id":"Q3968876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$E9EC60BC-D493-4372-A3B1-D7C5B08585E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"599c5dbf52817fbbe5f2f15e33a96dc6ac97514e","datavalue":{"value":{"entity-type":"item","numeric-id":3908463,"id":"Q3908463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$6F19B459-26CB-439B-BB56-4B70340ECA0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13354f860f564233e3fdc040eb05000a09a267ad","datavalue":{"value":{"entity-type":"item","numeric-id":1057264,"id":"Q1057264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$8484BDB9-04F7-41F0-981E-0E4501CBBC57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2266586$562B22F9-3F79-411F-B3E0-0C832115F647","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d00379ae7b1e9c23bf67cff2752d6182a89274d","datavalue":{"value":{"entity-type":"item","numeric-id":578921,"id":"Q578921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c14633c8a1a314dd6b7363ab304e70132eba11d1","datavalue":{"value":{"amount":"+0.8648203","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$E6B00848-6EBA-4868-BCAD-F4C5D9B6FE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d8303a30c9a6018acf0bbf1328bdda51112b9f1","datavalue":{"value":{"entity-type":"item","numeric-id":579319,"id":"Q579319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2c94ad07d7a4d6439b7fd288329e62edf4e9f70f","datavalue":{"value":{"amount":"+0.8128536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$8F7F2EF6-31E6-47DD-B78B-72822EA4A09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34d6ef23e0f24ccaaa853262a9bdfa178ef96a09","datavalue":{"value":{"entity-type":"item","numeric-id":5231711,"id":"Q5231711"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f1a8078761a2a4cfe4b064978e415f9cf61e8f9","datavalue":{"value":{"amount":"+0.8127254","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$EFDAB174-58C9-459E-801D-B417D0E15A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d067342e9afc343e31d937453dd33d62686fed6f","datavalue":{"value":{"entity-type":"item","numeric-id":4509291,"id":"Q4509291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a18487d3a0a5ecab06ea2a56b6001167251dd40","datavalue":{"value":{"amount":"+0.8109949","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$13125D0A-4BA8-4486-B102-4F1765915CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e864c8d7dd216e36316c93b3fe679c7b5a7b1ce7","datavalue":{"value":{"entity-type":"item","numeric-id":2391098,"id":"Q2391098"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7e52f9ccc44318fab24ba4922e90d48101a1856","datavalue":{"value":{"amount":"+0.80970544","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$76EE6564-3B7F-4BF3-8ABE-7E5E6B4CC142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"adad753f20cff46472daa392942a4893bd569c35","datavalue":{"value":{"entity-type":"item","numeric-id":706005,"id":"Q706005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"437c4643b7a1209d7ba418f1ce788cd1d9af9a07","datavalue":{"value":{"amount":"+0.7992244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2266586$6FAF21A9-918C-4192-9AC7-4B3FD6D8BFB1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Cancellation rules and extended word problems","badges":[]}}}}}