{"entities":{"Q5959738":{"pageid":8136540,"ns":120,"title":"Item:Q5959738","lastrevid":47766856,"modified":"2026-01-02T15:37:46Z","type":"item","id":"Q5959738","labels":{"en":{"language":"en","value":"On computing the size of a lattice and related decision problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1726721"}},"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":"Q5959738$1D7C24BC-D37B-4387-A121-C4FEC4B2EE7B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1c0ed23320f0fb6c99c51ca42e46fd842593bd1b","datavalue":{"value":{"text":"On computing the size of a lattice and related decision problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5959738$F792DE8B-B17B-4B70-AFFD-E189D1F1D500","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"594368b6f5a30f7042a45a5216e57bb2cafd5b37","datavalue":{"value":"0991.06006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$7E604808-5ABD-4DEB-AAD6-CB3E63FC3127","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"828868ad2e39078ad55097e6f5256e1866bed804","datavalue":{"value":"10.1023/A:1013970520933","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$E59E0BE7-AE6B-4B6C-BFD0-9746792754F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"66bcff630751ab3cb16accaecabac86d5f5a6611","datavalue":{"value":{"entity-type":"item","numeric-id":238862,"id":"Q238862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959738$3FE82FC2-576E-4BD6-816B-E90EC8840EFE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959738$FF059922-D84D-4210-AE22-DD72F3CE2BD3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d18439a648c68971434e67c4d3438eb872bd034f","datavalue":{"value":{"time":"+2002-04-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5959738$193815BC-4C0C-4BC2-8692-24281ADA75E0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e18871874ee83b93a55eb5f7e6b3271ce64d8e5","datavalue":{"value":"A triple \\(K=(G,M,I)\\) is called a context if \\(G\\) and \\(M\\) are sets and \\(I\\subseteq G\\times M\\) is a relation. For a context \\(K\\) define a Galois connection for \\(A\\subseteq G\\) and \\(B\\subseteq M\\) such that \\(A'=\\{m\\in M\\); \\(\\exists g\\in A\\), \\((g,m)\\in I\\}\\) and \\(B'=\\{g\\in G\\); \\(\\exists m\\in B\\), \\((g,m)\\in I\\}\\). A pair \\((A,B)\\) where \\(A\\subseteq G\\) and \\(B\\subseteq M\\) is said to be a concept of a context \\( K\\) if \\(B=A'\\) and \\(A=B'\\). It is proved:   a) the problem to find the number of all concepts of a given context is \\#P-complete;   b) the problem to decide whether for a given context \\(K\\) and a natural number \\(k\\) there exists a concept \\((A,B)\\) of \\(K\\) with \\(|A|=k\\) (or \\(|B|=k\\)) is NP-complete;   c) there exists a polynomial time algorithm to decide whether for a given context \\(K\\) and a natural number \\(k\\) there exists a context \\((A,B)\\) of \\(K\\) with \\(|A|\\leq k\\) (or \\(|A|\\geq k\\), or \\(|B|\\leq k\\) or \\(|B|\\geq k\\));   d) the problem to decide whether for a given context \\(K\\) and a natural number \\(k\\) there exists a concept \\((A,B)\\) of \\(K\\) with \\(|A|+|B|\\leq k\\) is NP-complete;   e) there exists a polynomial time algorithm to decide whether for a given context \\(K\\) and a natural number \\(k\\) there exists a concept \\((A,B)\\) of \\(K\\) with \\(|A|+|B|\\geq k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$43440665-12BE-4928-BC2F-091E20A79603","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959738$32EE508C-3472-4FBB-B0A4-BFAF6A8132EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7a7c57a22810c1fc3e6e7843b0557275bc4a46fc","datavalue":{"value":"06B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$916EE7A4-7976-469B-B021-F4A05D983A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$4ACE2C85-309B-4491-B256-B75108176782","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$39B8725E-2808-4DA3-A516-EC0D7D8A8C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"798cc93af1af672fcddaa0ab93cef1e0a30d7b36","datavalue":{"value":"06A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$64BD0AA4-1FAD-4A12-803D-2AFCD6970F00","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"987b5d2b4d28db805794de4f2ba68044bb0c28a0","datavalue":{"value":"1726721","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$BE17040B-55A3-4C19-8F0C-C6CFD12D8201","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d668889f77f3e419bed3147b829f1a444275662","datavalue":{"value":"context","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$17E40B44-EA6C-408B-9834-8FD3B7FD3B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b886cb0f6fc5f69fe9b63d329596cf05161a0ca","datavalue":{"value":"concept lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$771EC778-F43E-469F-9606-D5F37A937D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"077b8a4d862274302312144342c07fc43e1c07ed","datavalue":{"value":"complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$180E4DC7-C5A5-47A8-8706-E5BDA8FD3FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$164292F7-D2C2-4D5A-BA4C-375122180D2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7578b038a259e5bc1908dc999ebeaa3bdad3b25c","datavalue":{"value":"Galois connection","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959738$12381906-B42C-4098-892C-E21166124960","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":"Q5959738$34A19939-39F8-43F1-BAC9-60D1657F9287","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"57ac54e9518481570e53d2e6b9c092a910fbf1f8","datavalue":{"value":"https://doi.org/10.1023/a:1013970520933","type":"string"},"datatype":"url"},"type":"statement","id":"Q5959738$1AF385BD-F415-4017-B492-ADD268ECE417","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f7c0f6808a2e803185ffcb53d8190345860875d3","datavalue":{"value":"W277700758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959738$F0C37E9C-D49A-4165-AE22-2F9BA2D498B5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb3d8e8632186e19e7a6bc64043d194bc2c28ba9","datavalue":{"value":{"entity-type":"item","numeric-id":3552285,"id":"Q3552285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ceacce8674b0050dd839b9aa4948ead8109274f","datavalue":{"value":{"amount":"+0.7885283827781677","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":"Q5959738$7ECB3A02-691A-4AC5-A437-EEA7F0897448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7743509492f87cf8eabb664e950710994fb623b1","datavalue":{"value":{"entity-type":"item","numeric-id":5898505,"id":"Q5898505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2da83e8ba58dff75374c81ded51704508583135","datavalue":{"value":{"amount":"+0.7727171778678894","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":"Q5959738$5EAA7B23-5484-44E1-9D89-5DCCC7173CC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa9de57f0f1d16b82fbd07adb08b7876a7079a36","datavalue":{"value":{"entity-type":"item","numeric-id":676803,"id":"Q676803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbe84be4493c645dde29418c1d808e9c0e470de7","datavalue":{"value":{"amount":"+0.7658599019050598","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":"Q5959738$E4D277F7-A43B-4A99-B9AB-2BE198D90AAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5b11077456bd235d0ac6b1ce536dbb2bb0a0762","datavalue":{"value":{"entity-type":"item","numeric-id":4981123,"id":"Q4981123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5271ee7532d8c4987ba32a52242dd11f2e32d95","datavalue":{"value":{"amount":"+0.7649452686309814","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":"Q5959738$16C06D05-6019-4655-90D2-D8E92BB016D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a497313ea2913b2ff4033fdc5069fd2c3fcc27c","datavalue":{"value":{"entity-type":"item","numeric-id":4877294,"id":"Q4877294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"451efe49a2ed8256624ff933234c5322ecf21989","datavalue":{"value":{"amount":"+0.7642331123352051","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":"Q5959738$D30F457C-D266-4F9A-9E79-4D984DD333EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5959738","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5959738"}}}}}