{"entities":{"Q685454":{"pageid":687303,"ns":120,"title":"Item:Q685454","lastrevid":78189017,"modified":"2026-05-06T10:59:59Z","type":"item","id":"Q685454","labels":{"en":{"language":"en","value":"M\u00f6bius functions and confluent semi-commutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417376"}},"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":"Q685454$954A541D-6B6A-4C5D-BEAE-894FBE4983E3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3bbf131fe668d015da20b660d3ba310f2f9fae71","datavalue":{"value":{"text":"M\u00f6bius functions and confluent semi-commutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685454$B24578C4-BEAD-4B2F-B766-9125D326E82B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bccb7b79c6222c103659ad9cffc2073b96aa5610","datavalue":{"value":"0777.68052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$DAC4C6CA-90C7-494D-B554-E333A658DC05","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7836594ad0713af99c65d860dbf33bcf55acc89","datavalue":{"value":"10.1016/0304-3975(93)90229-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$9B8276F8-F493-4383-A71E-E68F5A7ABEDB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"81c83c28843efefafe1f80734e19c2e6ff309a9c","datavalue":{"value":{"entity-type":"item","numeric-id":213104,"id":"Q213104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$7394B10A-2751-4022-B29C-436FAF13C781","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$9B91901F-3532-4502-94F9-909D75BA183E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92112234a474f78049341bfb55637019f67e54ac","datavalue":{"value":{"time":"+1993-12-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685454$0BC8996B-8B0E-421B-BB6A-CA2767A8FF69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"afa35cd5537635752bdf0da947e99d4058ecf0d5","datavalue":{"value":"The paper studies liftings of M\u00f6bius functions of free partially commutative monoids. These functions have been of central interest since the beginning of the theory of partial commutativity by \\textit{D. Foata} and \\textit{P. Cartier} [Probl\u00e8mes combinatoires de commutation et r\u00e9arrangements, Lect. Notes Math. 85 (1969)].   The paper shows that their is a canonical one-to-one correspondence between unambiguous liftings and confluent semi-commutations. Thereby it establishes a new bridge from combinatorics on Mazurkiewicz traces to the theory of rewriting systems. The result has been conjectured by the author [Lect. Notes Comput. Sci. 317, 176-187 (1988; Zbl 0707.68049)], but it was solved only when a graph theoretical characterization of the confluence of semi-commutation became available by \\textit{V. Diekert}, \\textit{E. Ochmanski} and \\textit{K. Reinhardt} [On confluent semi-commutation systems -- decidability and complexity results, in: \\textit{J. L. Albert}, \\textit{B. Monien} and \\textit{M. Rodriguez Artalejo}, eds., Lect. Notes Comput. Sci. 510, Springer-Verlag (1991; Zbl 0753.00027)].   The paper concludes with complexity results showing that various decision problems about liftings of M\u00f6bius functions are complete for natural complexity classes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685454$9E4203E7-0643-4848-AD57-2C80BE5B7069","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$771D41E8-B314-4C0B-87B4-40712BFB33AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$0CC4B909-0B2D-4106-A2E4-86AA1023D252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"21699a423435669f291d1bd1ba3da28fa1465b3f","datavalue":{"value":"03D03","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$182BAF9C-EE3E-41C9-A9DA-97DA99491903","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4cc721f5e557e262df3d87aefe33d74033665f2e","datavalue":{"value":"417376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685454$106EEE31-DB00-4B4F-8510-2F28D0637FA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c00c376b18acb3f71935c4e597375155d26f7bb3","datavalue":{"value":"M\u00f6bius functions","type":"string"},"datatype":"string"},"type":"statement","id":"Q685454$DB993704-352E-436C-A3B9-64D0BF86C024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"95e39b1d3a00eeb3b9138a8fe05a514098d659a6","datavalue":{"value":"commutative monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q685454$059EAE66-CC36-4904-BB0C-8B204E0A3C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ed07919d1b866f2d751edc03157201edfe74ce3","datavalue":{"value":"liftings","type":"string"},"datatype":"string"},"type":"statement","id":"Q685454$1A41AB77-5A4F-4D20-AED5-1A49B8BB37E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b38049d159af5d6c62de79db7ea882fef0c299bd","datavalue":{"value":"confluence","type":"string"},"datatype":"string"},"type":"statement","id":"Q685454$776C98B7-DA6B-4698-BBB7-8506988F9CD4","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":"Q685454$4E6B6E23-9080-44D4-BBDD-172BEE93A273","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":"Q685454$F01A8F81-8133-4C60-A82D-3B60AE40A4D2","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":"Q685454$3B3A4014-CC31-4E12-9F1E-C4D91DFDF212","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"939096901dcc84a18ead69a18c121f4b42626e35","datavalue":{"value":{"entity-type":"item","numeric-id":584429,"id":"Q584429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$D888579D-E75B-400D-BEC6-91027183F9EC","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":"Q685454$CD750158-5FFF-42FF-B5EF-C1FAD2CCB5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d54b64b7f0b1105526a52223cf7a718e12ddecb","datavalue":{"value":{"entity-type":"item","numeric-id":3489462,"id":"Q3489462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$8E0656CC-E11E-44CE-9252-1F968A6F32BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c3224b3ee4e2065842acb7ecef1d84c9102fafc","datavalue":{"value":{"entity-type":"item","numeric-id":1188891,"id":"Q1188891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$2954BA6A-A69E-4ECC-AC41-1DE81736C083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21621c9670fb377eea8d9f5524a9b686b0e0b39c","datavalue":{"value":{"entity-type":"item","numeric-id":4036566,"id":"Q4036566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$24BCEB02-DF2A-4D60-ACCF-E199EDDC0DD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$47474577-5B5E-483B-83C7-03147C46BB1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d88eaa321dbf6e0bc6cb3537a7bf6c54848da5eb","datavalue":{"value":{"entity-type":"item","numeric-id":923133,"id":"Q923133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$AF30FB11-8747-49E8-AFD3-459548088B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c41017e4d7ed17afd6804c4f5a85dd25be34089","datavalue":{"value":{"entity-type":"item","numeric-id":4347971,"id":"Q4347971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$BE4E9D93-7F68-477E-860F-3EF7CA0FBF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1c3dda9d5cd14bb2805b0fe5628c94533820d0b","datavalue":{"value":{"entity-type":"item","numeric-id":803150,"id":"Q803150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$2E6C7908-A414-4901-90D2-814BAF6DC5DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e355586df730cb27f10a2d86578a8911e592d71","datavalue":{"value":{"entity-type":"item","numeric-id":4347974,"id":"Q4347974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$57EF730A-91EE-4E7D-BD77-6458DB93C305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7db5eb581c5550fe9f1aaa6318cbc6f909c56173","datavalue":{"value":{"entity-type":"item","numeric-id":3771629,"id":"Q3771629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$B0A1C5FE-53BF-412B-9CB1-ED4A0FC362A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51f4bac577a64da3e0f5b00fa0cb5bd1193d03ad","datavalue":{"value":{"entity-type":"item","numeric-id":1108811,"id":"Q1108811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$81C74C66-5AEF-45C9-9A5B-78B595231F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224fe5205d72f8b7bf3d1117c14acd86046e588d","datavalue":{"value":{"entity-type":"item","numeric-id":2652528,"id":"Q2652528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$D0117890-D86D-4A2C-807A-3894B5917F61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"90c8276902c931425fe70aa25358c9cac3acfa78","datavalue":{"value":{"entity-type":"item","numeric-id":4734770,"id":"Q4734770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$23070734-2B75-495B-87C6-4370E19CA2B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d54a9d73e487ba39fbe68740b0110b6ec7e322d","datavalue":{"value":{"entity-type":"item","numeric-id":3779772,"id":"Q3779772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$84308180-5A9D-4FD9-A069-81FEA447F4EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ece71e76af592c683383f9771dcf16661906206","datavalue":{"value":{"entity-type":"item","numeric-id":4035263,"id":"Q4035263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$49A50431-35F6-4667-BA51-76D3BBAF9573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"176b878b32dd9698208225bb09fc4b5ae95cc597","datavalue":{"value":{"entity-type":"item","numeric-id":1105040,"id":"Q1105040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685454$1E1C4C68-0A16-475A-8580-4C3D6F7E856E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6af5035c8cafca18aae0fdfa752ab874e36b23b","datavalue":{"value":{"entity-type":"item","numeric-id":4347971,"id":"Q4347971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3a07a3036bc1f0372a3ba4a3c1530a1b1dc4f4a","datavalue":{"value":{"amount":"+0.8503981232643127","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":"Q685454$800E3D51-417E-44A4-861B-296DB72EAF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a0676b3f8ad8e2455eef75d6abf1c2514633c9b","datavalue":{"value":{"entity-type":"item","numeric-id":4284225,"id":"Q4284225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7078c36d6869889301460c0fd8064dcb6f726d35","datavalue":{"value":{"amount":"+0.8227242827415466","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":"Q685454$3FB9DAB2-8EB6-48BB-BC51-3A0A02C2CCE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0db027bde7e0a54609bf31ccaeba705840b3f329","datavalue":{"value":{"entity-type":"item","numeric-id":2497971,"id":"Q2497971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"852dfaefc4fa24ea1b1c91454d8131a08f525631","datavalue":{"value":{"amount":"+0.822167694568634","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":"Q685454$E078D91E-96D7-402D-ABA4-20A124CC44D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b424bacb0b60a019776cb06ef0c0c8b8a32dec8c","datavalue":{"value":{"entity-type":"item","numeric-id":5948059,"id":"Q5948059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f35a323a0f16aaa5cca607e3ae6fe7b50649fef","datavalue":{"value":{"amount":"+0.816161572933197","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":"Q685454$67AB3407-A548-4D2B-BF1F-B9EF18B336E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63b8abdf07dcd5076fd8b4939272f5a1d558a515","datavalue":{"value":{"entity-type":"item","numeric-id":4035263,"id":"Q4035263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e068d3c49e8216eb8925277fdac6e2a9c6a0ca4c","datavalue":{"value":{"amount":"+0.816124439239502","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":"Q685454$4EBB4E53-CA36-4919-9CF3-43C0A501B409","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"M\u00f6bius functions and confluent semi-commutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/M%C3%B6bius_functions_and_confluent_semi-commutations"}}}}}