{"entities":{"Q1210296":{"pageid":1221045,"ns":120,"title":"Item:Q1210296","lastrevid":69906321,"modified":"2026-04-13T11:08:22Z","type":"item","id":"Q1210296","labels":{"en":{"language":"en","value":"Deciding whether a finite set of words has rank at most two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 178040"}},"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":"Q1210296$FBB356A6-2A69-40AF-926E-C9B9AD81EFE1","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8c88290fae87a5de36106a6f1be0770a713c0432","datavalue":{"value":{"text":"Deciding whether a finite set of words has rank at most two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1210296$B88AD268-3CCD-41F5-AFA5-222AA16D94EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb04703fd3cb4ed85f51acc5f3ff5c3bca6900ab","datavalue":{"value":"0798.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210296$8E580F2F-DE84-4F54-B74C-149A8212A390","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6281017cf2618b5a18bf734cfc6d208000747a47","datavalue":{"value":"10.1016/0304-3975(93)90023-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210296$D1213EB7-A598-44F5-A46E-DBE701FA2956","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":"Q1210296$9DAC541F-5AFB-4086-AB2A-CD26344818C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"03c5731f5d94178498d0ad4e21aec8fa89a18c16","datavalue":{"value":{"time":"+1993-05-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1210296$6B1257FB-B8E1-4855-890D-54FA57609630","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1e27c4e7abf473e5e7e76f05f2f1c1098d838f74","datavalue":{"value":"Let \\(X\\subseteq A^*\\) be a finite set of words over the alphabet \\(A\\). The rank \\(r(X)\\) of \\(X\\) is the smallest size of a set \\(Y\\subseteq A^*\\) of words such that \\(X\\subseteq Y^*\\). The author presents an algorithm to check the condition \\(r(X)\\leq 2\\). This algorithm works in \\(O(n\\log^ 2 m)\\) time, where \\(n\\) is the sum of the lengths of words in \\(X\\) and \\(m\\) is the length of the longest word in \\(X\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210296$DF071798-AC81-4226-A45E-4072B82E1255","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210296$6702780A-6AA3-491B-AE39-7BFDFF4CB46B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210296$E81C7453-C166-4A1B-A143-DCAC2D19C9DA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"85fb8ac90347a595bd6a7a0c21f92d0f56c9056f","datavalue":{"value":"178040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1210296$015D0B45-2FD1-4DD5-A77A-2293DBFA4D1B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b489be36f2806b138f130171c2492c208d47cd2","datavalue":{"value":"free semigroup","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210296$BDB7D800-FE21-4545-B305-DDCBFC5B3021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210296$56B89916-4EDD-4F54-AA95-BC3D48D2167E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e85686c88b6675116cec177bbafff890f9021164","datavalue":{"value":"rank","type":"string"},"datatype":"string"},"type":"statement","id":"Q1210296$9B81C263-518A-40C7-92A5-3AACE913091A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d06c94fbe1783ccdd89275c5891a96106217c32f","datavalue":{"value":{"entity-type":"item","numeric-id":782606,"id":"Q782606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$832B2EAC-C952-494E-BC88-8C958DC85920","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6e0db3e87cf0564d4c180dc3531c145e91e81ccd","datavalue":{"value":{"entity-type":"item","numeric-id":1806108,"id":"Q1806108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$1CE3DB24-EDFD-4A3D-BD16-4514C5CCEC2E","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":"Q1210296$716F5264-DBF9-4638-B12F-CB52737297DB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f914a0125fbfcefa866a5094ff6a5d2318079f","datavalue":{"value":{"entity-type":"item","numeric-id":4430300,"id":"Q4430300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$6DEF5692-FAA9-471A-BCCF-D6157E63C486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d40691ce6cf0d5bcb9135bc062b62084b420222b","datavalue":{"value":{"entity-type":"item","numeric-id":1132974,"id":"Q1132974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$CA81610D-84E4-4893-9427-3C149F180BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45a6cc612cd69e71b2b1680c5fce10af5da3602a","datavalue":{"value":{"entity-type":"item","numeric-id":3901701,"id":"Q3901701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$60FB3487-F7F4-43E7-A97B-34F5156B5E28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e1125662e806523c3fe140d59a9cf3b80a00c14","datavalue":{"value":{"entity-type":"item","numeric-id":1090421,"id":"Q1090421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$40015E62-8507-4E32-B122-9B435C9BBC57","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":"Q1210296$18BD7A1F-B1F8-4110-9478-C5054CDD10CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$108CDC4D-7B3A-4456-9B16-7DC6866AA78E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11afdffbe0e56d5432c3bf904f58d41a1f7cd998","datavalue":{"value":{"entity-type":"item","numeric-id":3484360,"id":"Q3484360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$76A4244C-C53C-4009-A01E-5F98E46FA948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b0c49f1598c41671e369ce5e6db3e547ddfe3bd","datavalue":{"value":{"entity-type":"item","numeric-id":1822632,"id":"Q1822632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$A63DB8B1-6B26-4192-A36F-4AA26E987D4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b9d6d3824965c3ff0f77d4ce51ebb822fa9c2ba","datavalue":{"value":{"entity-type":"item","numeric-id":1193899,"id":"Q1193899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$A9A40D75-AB6F-4FA4-83CE-2782C06E014B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"983c6d361b39a1c2df39031e508b7ae6b374912a","datavalue":{"value":{"entity-type":"item","numeric-id":4385527,"id":"Q4385527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$3014D74A-502E-43E3-B376-870F4FC28271","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a38983994d370e8a720ddf6cc1f7b76354ca36d","datavalue":{"value":{"entity-type":"item","numeric-id":3921412,"id":"Q3921412"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$C7E6F3C1-359D-400D-A9AF-C7C42D6B79DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c84c6b7f6a85a8a189245906ea50b9346fb10ad0","datavalue":{"value":{"entity-type":"item","numeric-id":3737376,"id":"Q3737376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$A79F7241-156E-4B18-AA7E-9B126ABDF92D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b548b6af06af9dabe6521e7d0f8ad83cdc203c3f","datavalue":{"value":{"entity-type":"item","numeric-id":5625457,"id":"Q5625457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1210296$2FF79892-62B2-49DB-A1C7-3449BC70E84F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44a5bf80a7135783c88230b1367b555c70526c22","datavalue":{"value":{"entity-type":"item","numeric-id":3484360,"id":"Q3484360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15508934b2953f7ee87910adfb07a5650e9f49bf","datavalue":{"value":{"amount":"+0.7732546925544739","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":"Q1210296$B152D63C-AB54-472F-B63A-5809A67BBF9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da7709cd625cc422bb236c5706ad8bb51c30109e","datavalue":{"value":{"entity-type":"item","numeric-id":3974875,"id":"Q3974875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf6b4f2f8f712afdf923e0b00b5edbfee2ecc665","datavalue":{"value":{"amount":"+0.740188717842102","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":"Q1210296$D55654D4-035E-4BBC-8362-F26D763421AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3719017dea117ea42053bad00724a3e5bf06cc0","datavalue":{"value":{"entity-type":"item","numeric-id":2333030,"id":"Q2333030"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7b0b1d45c314860bc198a7e75e51007410d8afe","datavalue":{"value":{"amount":"+0.7361231446266174","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":"Q1210296$ACEEA628-AC3F-43EC-96D5-8EC2BF0AAFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"385cf7e76f99167dcee5200ebca0e869c16fce92","datavalue":{"value":{"entity-type":"item","numeric-id":305772,"id":"Q305772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"890b8b86bf71989a4944e1e091900cc8223a9534","datavalue":{"value":{"amount":"+0.717380702495575","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":"Q1210296$E52ABD9B-5A7D-4CD9-8A33-E57CB1F1CF5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2846cbea094bbee44114b01e3f4b08870691919f","datavalue":{"value":{"entity-type":"item","numeric-id":1822632,"id":"Q1822632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91a368ec8b0ba6a127a6c867490ef73a2a8e5196","datavalue":{"value":{"amount":"+0.711537778377533","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":"Q1210296$747A2E5B-A2DE-4F3C-B516-4834E260E25B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Deciding whether a finite set of words has rank at most two","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Deciding_whether_a_finite_set_of_words_has_rank_at_most_two"}}}}}