{"entities":{"Q2577758":{"pageid":2588501,"ns":120,"title":"Item:Q2577758","lastrevid":57966648,"modified":"2026-04-03T06:47:42Z","type":"item","id":"Q2577758","labels":{"en":{"language":"en","value":"On closed sets of relational constraints and classes of functions closed under variable substitutions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2243901"}},"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":"Q2577758$3C02BF08-1BCF-40AA-AE54-581D4D3EA8FE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb4e7366251055da7a8846127167f9f6270ef1f0","datavalue":{"value":{"text":"On closed sets of relational constraints and classes of functions closed under variable substitutions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2577758$6BFC92D1-197F-4E81-9AA5-DB5595E0F891","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05fd47341e3a8197fde7347affa62a9f7cff5178","datavalue":{"value":"1095.08002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$E7DA74DB-6CC2-48AF-AB1C-F6426A78F9B7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"22ee8e74264b97280281ca9a75d0b37d2891d2eb","datavalue":{"value":{"entity-type":"item","numeric-id":251911,"id":"Q251911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577758$78C786BF-C557-439E-8A74-3E4C50F02246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e0d396f606a665365a09af31e721db21e4865cc","datavalue":{"value":{"entity-type":"item","numeric-id":168841,"id":"Q168841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577758$0D1FF4EF-171F-444F-A5F1-B789870A52E8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8fa179c8715004e2374d4db0c3ce41b39558e95d","datavalue":{"value":{"entity-type":"item","numeric-id":178112,"id":"Q178112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577758$FC30ECCC-07EC-40EA-A9C5-AA9AD6264A45","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a28896e5111b14a787c7b95f92ad273263b18f84","datavalue":{"value":{"time":"+2006-01-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2577758$9E988CD6-0D2D-41A2-BE9E-CCBCC40F64E7","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec5741ee11ae7aa9f1583e2249450728caa099d4","datavalue":{"value":"https://arxiv.org/abs/1508.01558","type":"string"},"datatype":"url"},"type":"statement","id":"Q2577758$C48ABF10-99DC-4523-B129-2471D9C41803","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b6553bbb80109e38869532a340b88520f14dd06e","datavalue":{"value":"Let \\(A\\) and \\(B\\) be arbitrary non-empty sets. If \\(\\ell\\) is a map from (ordinal) \\(n\\) to (ordinal) \\(m\\) then the \\(m\\)-ary function \\(g:A^m\\to B\\) defined by \\(g(\\underline a)=f(\\underline a\\circ\\ell)\\) for every \\(m\\)-tuple \\(\\underline a\\in A^m\\) is said to be obtained from the \\(n\\)-ary function \\(f:A^n\\to B\\) by simple variable substitution. A class \\({\\mathcal K}\\) of functions of several variables is said to be closed under simple variable substitution if each function obtained from a function \\(f\\in{\\mathcal K}\\) by simple variable substitution is also in \\({\\mathcal K}\\). Further, under an \\(m\\)-ary \\(A\\)-to-\\(B\\) relational constraint is understood an ordered pair \\((R,S)\\) where \\(R\\subseteq A^m\\) and \\(S\\subseteq B^m\\). A function \\(f:A^n\\to B\\), \\(n\\geq 1\\), is said to satisfy a constraint \\((R,S)\\) if \\(fR\\subseteq S\\). A class \\({\\mathcal K}\\subseteq\\bigcup_{n\\geq 1}B^{A^n}\\) of \\(B\\)-valued functions on \\(A\\) is said to be definable by a set \\({\\mathcal S}\\) of \\(A\\)-to-\\(B\\) constraints if \\({\\mathcal K}\\) is the class of all functions that satisfy every member of \\({\\mathcal S}\\). Galois theory of finite functions and relational constraints developed by \\textit{N. Pippenger} [``Galois theory for minors of finite functions'', Discrete Math. 254, 405--419 (2002; Zbl 1010.06012)] is extended to the infinite case. It is proved in particular that a class \\({\\mathcal K}\\) is locally closed and is closed under simple variable substitutions iff \\({\\mathcal K}\\) is definable by some set of \\(A\\)-to-\\(B\\) constraints (Theorem 2.1).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577758$8F7086F7-0EA9-4BE5-B384-7046C63F30E8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"92a555e3a541c9f0978c54443cf0a96e2a43c4df","datavalue":{"value":"08A02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$797CE7EF-87A8-4BB0-AAAE-E19F3C08E815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"798cc93af1af672fcddaa0ab93cef1e0a30d7b36","datavalue":{"value":"06A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$5FAEC261-38FB-494B-8302-4A87D4C89578","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"07d07aece6117999b9f73a0b5b740dcf276ec094","datavalue":{"value":"2243901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$98CB75EB-0906-4B27-B960-AAE8ACE9DC1A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c99d50cc03f9621e87d1300d87a92e1d2d58606e","datavalue":{"value":"Galois connections","type":"string"},"datatype":"string"},"type":"statement","id":"Q2577758$F647F0F1-2C48-4596-8219-3A1CE520943B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8a4269540e775ce717310028f86928e9eeea39c7","datavalue":{"value":{"entity-type":"item","numeric-id":241780,"id":"Q241780"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2577758$05408282-4C8C-48F6-91C3-08307EC9D08B","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":"Q2577758$4405C5B2-8088-4F92-B332-71B4C350D29E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d7c534f0154b9516b7441c0236e6ce0d85637dbf","datavalue":{"value":"W2963920170","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$CC24BA90-A81D-472D-BA03-1F41C4690B94","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0db457e0e38630c19203d94d70374634bff0ce82","datavalue":{"value":"10.1007/S00012-005-1933-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2577758$4B0B3A76-AACC-4CF4-A98E-3A2978BA28AF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"87dae50187c8d2f84bf23907aa1fb53f8305711f","datavalue":{"value":{"entity-type":"item","numeric-id":607451,"id":"Q607451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cbb6530fea0eee9e63f3ffb6f4357e76f05da9c2","datavalue":{"value":{"amount":"+0.8309292793273926","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":"Q2577758$ABE7E64F-3FE9-4E41-B9C9-93C23BA34980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"016b95edd2d6106395882ab4da800ad1d7d45df1","datavalue":{"value":{"entity-type":"item","numeric-id":334979,"id":"Q334979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d40a8d50421c438f5a64ac029521565fe3013f4a","datavalue":{"value":{"amount":"+0.7906454801559448","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":"Q2577758$76FBA98F-C32E-4E6E-90FB-B04AA80FD244","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e5105452f0bdcc59b23ab10c73914d71d88d5f","datavalue":{"value":{"entity-type":"item","numeric-id":4542607,"id":"Q4542607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b39bebf61a11a55429f195c9999307f7cbf703db","datavalue":{"value":{"amount":"+0.7799808979034424","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":"Q2577758$CE1C2B52-D220-4786-939C-4A70FDD13382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab2563c9994dc822633a2a05c117af280b3cbddc","datavalue":{"value":{"entity-type":"item","numeric-id":1613555,"id":"Q1613555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febcbebb46ea58718bcd3d30657c742ac8e60bc3","datavalue":{"value":{"amount":"+0.7769967317581177","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":"Q2577758$8D2E7B20-1556-4737-95FE-2A34E548C98F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"358f7d9d13c2174d8b4261ed91655818a164aed3","datavalue":{"value":{"entity-type":"item","numeric-id":1991603,"id":"Q1991603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"febcbebb46ea58718bcd3d30657c742ac8e60bc3","datavalue":{"value":{"amount":"+0.7769967317581177","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":"Q2577758$1D4FE18F-E22C-4C3E-91F5-781994E078F6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2577758","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2577758"}}}}}