{"entities":{"Q2640345":{"pageid":2651088,"ns":120,"title":"Item:Q2640345","lastrevid":49462924,"modified":"2026-01-07T05:06:53Z","type":"item","id":"Q2640345","labels":{"en":{"language":"en","value":"Efficient solution of some problems in free partially commutative monoids"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4187113"}},"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":"Q2640345$2BD805F4-D4F7-43C4-9485-7574F5F5910A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9c6f764a7ad9f690ee694aafd8d3963113d9b0b","datavalue":{"value":{"text":"Efficient solution of some problems in free partially commutative monoids","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2640345$9D7C358A-A600-4F36-B753-27C77155E3B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f7cafc7d0e14387d1bd4c679e6b8422409f881c4","datavalue":{"value":"0719.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$5F2E92F1-759E-417D-B0B4-EF451D96D4E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0e5a681c34ccd689138021b3a88a04f762ac01a2","datavalue":{"value":"10.1016/0890-5401(90)90010-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$F95C4859-DC9B-45CD-BD20-01C53FE86FA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$7876F3B8-BDFB-4F08-A3F3-CA6A03D7E4AE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$45321E9A-B87C-43AA-B789-FBDE630819DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2640345$600FBFD3-9ACB-4C71-A399-BA538BD6EF66","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c96fa336ba3831be84c67244546a5c406aef1b4","datavalue":{"value":"A partially commutative alphabet is a pair (\\(\\Sigma\\),\\(\\theta\\)) consisting of a finite alphabet \\(\\Sigma\\) and a binary relation \\(\\theta\\) in \\(\\Sigma\\) which gives the pairs of commuting letters. The free partially commutative monoid M(\\(\\Sigma\\),\\(\\theta\\)) determined by (\\(\\Sigma\\),\\(\\theta\\)) is the quotient monoid \\(\\Sigma^*/\\equiv\\), where \\(\\equiv\\) is the congruence generated by \\(\\theta\\).    The authors present and analyze linear-time algorithms for several basic combinatorial problems concerning such monoids. In the following brief descriptions of the main questions considered, a fixed monoid M(\\(\\Sigma\\),\\(\\theta\\)) is assumed.    (1) A nonempty word \\(y\\) is primitive mod \\(\\theta\\), if there is no word \\(z\\) such that \\(y\\equiv z^{k}\\) for some \\(k>1\\). If \\(x\\equiv y^{n}\\) and \\(y\\) is primitive mod \\(\\theta\\), then \\(y\\) is a congruential root of \\(x\\). Such a root can be found in time linear in the length of \\(x\\). Also, the related question whether two given words have some \\(\\equiv\\)-congruent powers can be answered in linear time.    (2) The generalized pattern-matching problem asks whether a word \\(y\\) is congruent to a factor of another given word \\(x\\). For this problem a linear-time algorithm which makes use of the Knuth-Morris-Pratt algorithm is given.    (3) Two words \\(x\\) and \\(y\\) are conjugate in the free monoid \\(\\Sigma^*\\) if \\(xz = zy\\) for some word \\(z\\), or equivalently, if there are words \\(u\\) and \\(v\\) such that \\(x = uv\\) and \\(y = vu\\). In the more general case at hand, these two definitions lead to different concepts, but for both of them linear-time algorithms deciding conjugacy are given. The paper is very well written and the extensive background knowledge used in the algorithms is also clearly presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640345$7FFC4811-C2B3-4671-B17A-9B85088ED515","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$E48495BD-A411-4DF7-857B-92C0F4975218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$1773AD9B-2A0F-4FD0-BBD5-C730F10E9495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$F10F94C3-6035-4A93-8951-E8EB7804E400","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$3AFC8CC8-A20B-493E-A68A-7A41F0EEE3AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"62eef3d316d25dc6b190396edd901c3f27aabbc5","datavalue":{"value":"4187113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640345$F87820AF-839B-469B-9998-7828F94D47A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"464d102cfb63856d182bfeef57c2d35a22bf8823","datavalue":{"value":"partial commutativity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640345$191CAA0A-3487-4E28-8A57-FDAA693B5EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7849268f7bb2fac3b272e91b7f02de428246451","datavalue":{"value":"commutation monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640345$703F586E-C456-4463-BF83-5B6E9F49FF22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f6ce889a8a92a5adf9884f2ba6068fac0f7d64b3","datavalue":{"value":"traces","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640345$C37056AA-AE65-471C-8456-6A080BA9AE3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640345$7640BA77-B8DC-4C07-A283-641582C6E279","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e07306c48ccd2e9c29ec0a26f6f3afb07223426","datavalue":{"value":{"entity-type":"item","numeric-id":591314,"id":"Q591314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$5C4E8516-6AF1-4647-8831-6E85288A65FB","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":"Q2640345$010BAB2E-B578-4D44-B22F-EABA63482784","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb3f3d4284f29707c15dbffe01b4356eafdc3d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1107296,"id":"Q1107296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$BD089D60-CFAB-4CFB-A483-D47CA12216FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$AB238AAD-F972-4D1D-B175-55321A8097D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4d0787b1cc5b37ced50aeab4d936b4e054af97e","datavalue":{"value":{"entity-type":"item","numeric-id":3659975,"id":"Q3659975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$85A51A25-5A42-4ADD-BF6E-3231F2482E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266e74dfc49b54318e6f3c94ba097b82b39ab983","datavalue":{"value":{"entity-type":"item","numeric-id":3947146,"id":"Q3947146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$7E11B6E0-4E24-40A4-8C4D-B6388FA2843A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e947664dc494a808b8d6cd2c56ed3d1b82c197fa","datavalue":{"value":{"entity-type":"item","numeric-id":1102124,"id":"Q1102124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$EA63745E-C366-46F3-BB2D-2FDBE6170881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2321ffc17406524f453e4fee8339197a12bf2512","datavalue":{"value":{"entity-type":"item","numeric-id":2536784,"id":"Q2536784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$DDBFE4BA-0210-49E7-83D6-C1958365B198","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efa1d9ec51d8e546e3d5a5823e053b5e9183e806","datavalue":{"value":{"entity-type":"item","numeric-id":2266128,"id":"Q2266128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$2B1EEC9F-F40B-4988-B0BC-E543FDAAED33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78b31a52389be07054ca875395c649c7b29fc713","datavalue":{"value":{"entity-type":"item","numeric-id":3736919,"id":"Q3736919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$A79E2558-43A3-4295-A05F-3694D6710C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cd43fc830113b2d5a880d847919d9f61546682","datavalue":{"value":{"entity-type":"item","numeric-id":1068945,"id":"Q1068945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$CE841AFF-0E20-45B6-92B9-9B608670B025","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f4b161773f1e9dee8773129f8a4840a7ed2e97b","datavalue":{"value":{"entity-type":"item","numeric-id":1084189,"id":"Q1084189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$0109B6F6-D513-4F58-82B7-7B73A23ED24F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fe91faead361908a57f5abb57ab434ee7f6c53c","datavalue":{"value":{"entity-type":"item","numeric-id":1062471,"id":"Q1062471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$D606BE92-2401-408C-AC09-25335D8E1758","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3928589bcc683b5d7a0601e7fcdcad9ba7d0589","datavalue":{"value":{"entity-type":"item","numeric-id":1838329,"id":"Q1838329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$F8D8485C-A2D0-449E-BC84-4AC6B8C6DED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ac5a46180e1dc4f153e26635681df86ec98c676","datavalue":{"value":{"entity-type":"item","numeric-id":5180826,"id":"Q5180826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$E5F2BF69-172D-4B77-87FE-91ADE3BDB84D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$A52B7B9F-DD46-4294-BB0E-9F0953ADFCDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe18fdfb882c799d34a7482b763d96a45625e71","datavalue":{"value":{"entity-type":"item","numeric-id":3853827,"id":"Q3853827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$48D3B4E2-65C9-4446-8577-0F84B418AF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$5C159880-6D76-44D7-A6DF-CC5B9FE06FDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa78d7638ea69d0a540e6d078b65b138e9b0f9b1","datavalue":{"value":{"entity-type":"item","numeric-id":801163,"id":"Q801163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$BEC8DB78-1140-4B59-BAB0-EBFB339E4CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6755a5ba9b0dffa9eb25b5ec62f1a57c213999a","datavalue":{"value":{"entity-type":"item","numeric-id":3738586,"id":"Q3738586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$C5EE719C-DE0A-4273-9681-EA16E9E4F9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9bf2a4ea24448d9119242381c3d6b7b77865a3db","datavalue":{"value":{"entity-type":"item","numeric-id":3469280,"id":"Q3469280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640345$624092F4-3C4A-4704-B20B-66859F220057","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"408fe2eda89ec0a525c0ded565dfa1012bcd400f","datavalue":{"value":{"entity-type":"item","numeric-id":3738586,"id":"Q3738586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52fcc3fe5b3d8a6be7edd576b064114289a75f57","datavalue":{"value":{"amount":"+0.8733574748039246","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":"Q2640345$46A81E2B-D94F-4522-8CFD-0274982F09D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aaf512ba4536c9369820e41d4784425e1b48a4cd","datavalue":{"value":{"entity-type":"item","numeric-id":1084189,"id":"Q1084189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04069651e211850bde6f03a849ae2391529fd42e","datavalue":{"value":{"amount":"+0.8679709434509277","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":"Q2640345$200E7E5C-30FD-48BC-842B-4597C95DF0F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db522d13b6a457586f78f2e4d1ce2d536dcadfaa","datavalue":{"value":{"entity-type":"item","numeric-id":1086682,"id":"Q1086682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e42f87bf433979ccb3abab24068ed9c590e492eb","datavalue":{"value":{"amount":"+0.8658632636070251","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":"Q2640345$DBEC34A0-4973-492D-BD74-057A43BDC43E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1ca99ea052d9cb8b119a24bc1c64076f4f615d5","datavalue":{"value":{"entity-type":"item","numeric-id":1068945,"id":"Q1068945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28bb9b84a50f7001d11f83c641dfe716bba77a25","datavalue":{"value":{"amount":"+0.8640410900115967","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":"Q2640345$75A1F886-FEEC-4215-A30E-A89BE3BC879B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fde02a2d55150c987cfddee45f5fd0dac1427a53","datavalue":{"value":{"entity-type":"item","numeric-id":3469280,"id":"Q3469280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"145d83d8bd8104c28f68cef28d7b54cfe78cf6d0","datavalue":{"value":{"amount":"+0.8633670210838318","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":"Q2640345$2DAB693E-907D-41FD-B14F-7094CA2AC4AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2640345","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2640345"}}}}}