{"entities":{"Q578921":{"pageid":580688,"ns":120,"title":"Item:Q578921","lastrevid":62914935,"modified":"2026-04-11T08:58:24Z","type":"item","id":"Q578921","labels":{"en":{"language":"en","value":"On the complexity of some extended word problems defined by cancellation rules"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4014057"}},"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":"Q578921$2DB3E1B5-E2B4-4C35-B419-A1D2DB75CE57","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4a57dc0a6665ddd5dd87ba295b286f623b674495","datavalue":{"value":{"text":"On the complexity of some extended word problems defined by cancellation rules","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q578921$009501D4-DD91-484A-80B6-EA780D9707F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa1f655d756f26a5081ed97e95ba8137632937e0","datavalue":{"value":"0624.68070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$720B2498-8954-4261-B491-70FEF6F4DE86","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"828d68694812e85255ca65ad6ffd64bfee46b811","datavalue":{"value":"10.1016/0020-0190(86)90087-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$C88A42C2-757A-4B38-88C8-F5A79502F36D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4de0c68638cfa703a054d37a06a7288247152965","datavalue":{"value":{"entity-type":"item","numeric-id":578920,"id":"Q578920"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$91649B63-B609-4B66-B704-D6DDDB275D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cfd137ab3986c6c9a1e6f54aff881bebe6c2d055","datavalue":{"value":{"entity-type":"item","numeric-id":505063,"id":"Q505063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$3ADE45B6-AD69-475D-BD66-F5625DE8BC2C","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":"Q578921$FD453750-5E33-4EC2-8FBB-D9C52D7F8062","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q578921$CB485058-8169-422C-9B3B-90F1D3EA06DE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e57b708a9b2deb344a64c56db6e729bc238fbfa","datavalue":{"value":"We give an algorithm which computes the set of descendants of a regular set R, for Thue systems of certain type. The complexity of the algorithm is \\(O(m^ 3)\\) where m is the number of states of an automaton recognising R. This allows to improve the known complexity bounds for some extended word problems defined by cancellation rules.","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$E95D9DA4-08FF-42DE-820A-07983F6E3482","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$8EDEEF10-D3ED-41D2-AF60-F2CEC94A112A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$996320DF-C1C0-46A9-BA38-877859E2C0C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79c9a014785e41c94f76c463174af5cf2a59ec70","datavalue":{"value":"03D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$1D998698-FF8E-4949-8DCC-8B9661A660C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$14DA3422-9564-43DC-B9AB-2A1EB7834930","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ea08991939aba7551a169e7d7bc27a6fdf5a2361","datavalue":{"value":"4014057","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$7A8C758F-BAA3-4D87-AACF-0D710437B9E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$31A38A3B-CA96-456F-ADCE-094092416571","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a554a8e2331f61a6ce2d3f04993b50044b47c8a","datavalue":{"value":"set of descendants of a regular set","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$CBD934E8-3BB5-4178-855F-5799B9B7B63B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"872431b5dc755bcd5b7213492e1cb5e11885541c","datavalue":{"value":"Thue systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$F40DFBD2-4BD3-49F3-8B67-46B5094EE62F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"900449d9c111228b32b61aefc4917c5119284013","datavalue":{"value":"complexity bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$997C8ADC-42A7-484B-9AA5-1AB1356FF7A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ba259c5c06af63100955fccf8bc8b370e89eaee","datavalue":{"value":"word problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$7EEFC1B8-7F4A-4EAA-AD75-2590679DD47B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a115300b75d53df3f1db5b0f1bc5e2a1d6a726f","datavalue":{"value":"cancellation rules","type":"string"},"datatype":"string"},"type":"statement","id":"Q578921$AEE21219-37CA-43DB-9440-43E33F0305DC","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":"Q578921$692512C3-7AA9-419F-A4D6-B3CA186ACE8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7a7e393f7543622e771cbc51b2eae0aabeebb39b","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90087-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q578921$8E927561-A1F3-4C6D-B8D2-157A50DE00D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"82413db70148e63e3f9270c92d70c9f1437eab26","datavalue":{"value":"W2019872646","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q578921$7CB12720-617D-457C-9621-B2B2819B9F5E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"84b60b6016e2874f3433a4a41cc31aafa6dd93fc","datavalue":{"value":{"entity-type":"item","numeric-id":5616207,"id":"Q5616207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$6BF4A1E8-67C4-4F56-A90A-C2EA9AA77A28","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":"Q578921$4B1BC29A-A07C-429A-88A4-760887A114F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8515c66e998b49e90d2f794c4c8b138d50aa183","datavalue":{"value":{"entity-type":"item","numeric-id":2266586,"id":"Q2266586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$06E11F80-B401-4A4A-AF32-47BB852B9288","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":"Q578921$1CD5BD5E-20B0-4170-8BFF-B49347B93216","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":"Q578921$56EBE4CF-230E-4632-B735-F8214A13C7AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d690f2ab325c2bb3fab04ea0f693e2d0af7b00","datavalue":{"value":{"entity-type":"item","numeric-id":2547595,"id":"Q2547595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$FC2DB2BF-AF36-4373-8087-14658947EB15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$6FA786AD-40E7-498F-98F3-D4304E54FB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6315d9cda93162c2aba33a1d3e5ec00f12fd74a","datavalue":{"value":{"entity-type":"item","numeric-id":5729523,"id":"Q5729523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$ED6ACA7E-D159-4C19-B126-AFEB9FE26B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b020801ec5e7b19d16baf8ec77b2baea503b33","datavalue":{"value":{"entity-type":"item","numeric-id":3267904,"id":"Q3267904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q578921$5337A5FA-C6EB-4582-B11B-DBECA6CCE6E2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7246596cb569f986ccca0a9439ed7cfe589ae8ce","datavalue":{"value":{"entity-type":"item","numeric-id":2266586,"id":"Q2266586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dea6518e3bc1b2f38acd7865cb58e7b0b2cddca8","datavalue":{"value":{"amount":"+0.8214384317398071","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":"Q578921$7A0D1D4A-EA83-4DBE-88B6-345C4E583252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1c626c937acc6aea17ef23965bc51c02c964c5ce","datavalue":{"value":{"entity-type":"item","numeric-id":1070349,"id":"Q1070349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"930cc4a787daccfd39e48e42d937baaadd79d734","datavalue":{"value":{"amount":"+0.7652971148490906","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":"Q578921$3B7F24B4-C56F-4733-AD0B-0F9CFB6AFC49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff8b476ba6d3381e826d40590cd2c4c53c7e17a","datavalue":{"value":{"entity-type":"item","numeric-id":3826535,"id":"Q3826535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd814729376ea4bb15eef1a0332083c6489a695c","datavalue":{"value":{"amount":"+0.7536805272102356","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":"Q578921$B3485FA2-C27A-44B3-8F3C-1494C7FD2E29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c4c9dc856dec54ff66f66fbbd9f1a467a7277cf","datavalue":{"value":{"entity-type":"item","numeric-id":2723899,"id":"Q2723899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6150542db80a78c9de66bdedebb4c7a77c3a819","datavalue":{"value":{"amount":"+0.7532945275306702","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":"Q578921$CDFB5E1B-FEBA-451A-BF0D-C556A527B93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"662e9133bdaf10925944fb1bafc2a3130572fe5f","datavalue":{"value":{"entity-type":"item","numeric-id":1763707,"id":"Q1763707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d4c9f92a5a0c91c90c81754889a192a340b3bdc","datavalue":{"value":{"amount":"+0.7516318559646606","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":"Q578921$86568220-CF26-468F-8FCF-5CE6A23AACFC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the complexity of some extended word problems defined by cancellation rules","badges":[]}}}}}