{"entities":{"Q2413194":{"pageid":2423937,"ns":120,"title":"Item:Q2413194","lastrevid":78783329,"modified":"2026-05-06T12:25:52Z","type":"item","id":"Q2413194","labels":{"en":{"language":"en","value":"Two variants of the Froidure-Pin algorithm for finite semigroups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6857310"}},"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":"Q2413194$AE8B9063-6A42-401F-B3C9-77C564F6DCF1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48e595446a47a86534b8d490ebb774039c4b6625","datavalue":{"value":{"text":"Two variants of the Froidure-Pin algorithm for finite semigroups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2413194$4F94FD42-705A-40DE-A85A-CFCD1E4937FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8901cbb7057b716262f429e430f686b022478d6d","datavalue":{"value":"1421.20020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$D1594DA4-BFF4-4ADF-9231-F86E1C6445AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0eb6f2e5c045981bb37e3922b1949f1b4b4482c9","datavalue":{"value":"10.4171/PM/2001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$61D68F27-D2C1-4D1B-BDA0-FD1016FBDE1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46c0c220d20864a64ce527e0430f14bd4889ed14","datavalue":{"value":{"entity-type":"item","numeric-id":1686301,"id":"Q1686301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413194$731FAAFE-D64A-4AD0-B66A-AE652496B51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1537c45749fde170b34adb6bf2e936507286bc92","datavalue":{"value":{"entity-type":"item","numeric-id":343473,"id":"Q343473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413194$423AE9C7-A6A9-4C1C-8E81-4E7C13B81F6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ee19ed06f09c9521c312c322455168c063f81fd","datavalue":{"value":{"entity-type":"item","numeric-id":306544,"id":"Q306544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413194$741A1B8B-C85F-4372-8FE1-0FB3900B1B81","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f0da1cb3a9fbcb78801361ca630307ed2635d6e0","datavalue":{"value":{"entity-type":"item","numeric-id":209011,"id":"Q209011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2413194$C0F94927-9FE1-4A2A-9293-468864ACCCDE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ee62bc46b4dd3703fb531c7141fdf043716c9e15","datavalue":{"value":{"time":"+2018-04-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2413194$D89D7482-A264-43EF-A967-1875EFE61452","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e97b3760f5dd8a0d1abeb8fa1783c45c41bb4e09","datavalue":{"value":"https://arxiv.org/abs/1704.04084","type":"string"},"datatype":"url"},"type":"statement","id":"Q2413194$45E71250-1FF9-47BB-ACAD-529E14F648ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72905ebb267e6978c4b49698dae508f2f361756d","datavalue":{"value":"Summary: In this paper, we present two algorithms based on the Froidure-Pin Algorithm for computing the structure of a finite semigroup from a generating set. As was the case with the original algorithm of \\textit{V. Froidure} and \\textit{J.-E. Pin} [in: Foundations of computational mathematics. Selected papers of a conference, held at IMPA in Rio de Janeiro, Brazil, January 1997. Berlin: Springer. 112--126 (1997; Zbl 0876.20034)], the algorithms presented here produce the left and right Cayley graphs, a confluent terminating rewriting system, and a reduced word of the rewriting system for every element of the semigroup.  If \\(U\\) is any semigroup, and \\(A\\) is a subset of \\(U\\), then we denote by \\(\\langle A\\rangle\\) the least subsemigroup of \\(U\\) containing \\(A\\). If \\(B\\) is any other subset of \\(U\\), then, roughly speaking, the first algorithm we present describes how to use any information about \\(\\langle A\\rangle\\), that has been found using the Froidure-Pin Algorithm, to compute the semigroup \\(\\langle A\\cup B\\rangle\\). More precisely, we describe the data structure for a finite semigroup \\(S\\) given by Froidure and Pin [loc. cit.], and how to obtain such a data structure for \\(\\langle A\\cup B\\rangle\\) from that for \\(\\langle A\\rangle\\). The second algorithm is a lock-free concurrent version of the Froidure-Pin Algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413194$842215E1-B51C-4395-A0D3-8BF888C6D823","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"da4486fba5293e43f43fa118be7b2896ee43bba4","datavalue":{"value":"20M10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$9099D945-7D7A-4FA9-B5DD-3A8A17C1938B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$79501E3B-C7D5-46C1-9FE4-F07AD2FCB4B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$87310B6F-2321-4B50-9EE4-78610FE7377B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"573f9c889bc5b7944d707c1f4d915ab8b82f7340","datavalue":{"value":"6857310","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$2F7148B8-2E62-4477-B6C6-76698A3A01F4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fcf2ec45b56911a8bbac4fb9d1dc61ba4b57469c","datavalue":{"value":"semigroups","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413194$AE490DEC-C562-4F9B-98B9-99D7E8F761F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0206b3ce899f46214672b76de6b4000dbeb8f6f","datavalue":{"value":"monoids","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413194$4C936D13-A9AD-45BF-B537-BAC561DFB6AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413194$02968F28-B61E-4277-978A-7CF320F4E9FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15ac95bace04be49f497cca43d0ba7f878233024","datavalue":{"value":"Green's relations","type":"string"},"datatype":"string"},"type":"statement","id":"Q2413194$4C4298C2-A9AA-4368-B391-2111F60158F7","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"54a72b160f2c3a18e4ddffa9c616d140e69ec455","datavalue":{"value":"Q57990346","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$A8DA50FD-3C43-4E2D-99E9-7C9FA4BD865B","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":"Q2413194$23B68896-AB04-4457-94AF-BFD2495296E8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"332a354f525a140be7043c040900613c62689c02","datavalue":{"value":"W2962922377","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2413194$2BEC1272-7156-432C-B612-1DE19F4C6337","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78d8f14e52915e5d19979548fb052cba1eb7216a","datavalue":{"value":{"entity-type":"item","numeric-id":4336094,"id":"Q4336094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bda4e0ff96e12e539eecf01ef0f846d1bac30b3","datavalue":{"value":{"amount":"+0.8434379696846008","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":"Q2413194$6F876388-EC41-4ACE-B7F4-1AA1BB1C180C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98c274cd1aa746e2c191af6ac21100581b78ea8c","datavalue":{"value":{"entity-type":"item","numeric-id":1757008,"id":"Q1757008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cd7b83c63132ebbd6b3349f8bec1d23353b8de2","datavalue":{"value":{"amount":"+0.7687944769859314","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":"Q2413194$5F26C343-9065-420F-96B1-DBD5481543B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55b0c14fcee4829ee2e6a3feead63741b0503c25","datavalue":{"value":{"entity-type":"item","numeric-id":1599539,"id":"Q1599539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd9c8ce6a25585d4f461f4dbf2447812c3001a2b","datavalue":{"value":{"amount":"+0.7628055810928345","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":"Q2413194$1A97AADB-8336-45B1-B09A-FEF30B56DFD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf6fede5bf4be6709503b0597b4e4c07cb4cbbdf","datavalue":{"value":{"entity-type":"item","numeric-id":846358,"id":"Q846358"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd9c8ce6a25585d4f461f4dbf2447812c3001a2b","datavalue":{"value":{"amount":"+0.7628055810928345","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":"Q2413194$A214F52B-2149-405A-9260-77C8D60AAA66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2634c61882337bda3018841014982eafc91feef","datavalue":{"value":{"entity-type":"item","numeric-id":1645462,"id":"Q1645462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51bc9ecbb5fcb9489713c59a45712536f8aefda1","datavalue":{"value":{"amount":"+0.758883535861969","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":"Q2413194$3295D893-0E66-429E-95C8-9B48068D7300","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Two variants of the Froidure-Pin algorithm for finite semigroups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Two_variants_of_the_Froidure-Pin_algorithm_for_finite_semigroups"}}}}}