{"entities":{"Q2354983":{"pageid":2365726,"ns":120,"title":"Item:Q2354983","lastrevid":57870399,"modified":"2026-04-02T21:28:05Z","type":"item","id":"Q2354983","labels":{"en":{"language":"en","value":"Topology of the view complex"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6465448"}},"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":"Q2354983$0BFC3BC6-3266-4961-AFBE-B9468ED1330E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ea6cb398feae6cf4ab6a8910d98992ab41736647","datavalue":{"value":{"text":"Topology of the view complex","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2354983$5CF86C1E-6599-41D1-BC6C-51C0DA70C7A4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c4264db2b9d76fab34289fad21926d090ec76e73","datavalue":{"value":"1327.55011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$5DC1E488-32BA-4B76-9149-AEE78C70658F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbe52a955fe87ebf7724ee2cb9164de8d0f8099b","datavalue":{"value":{"entity-type":"item","numeric-id":215085,"id":"Q215085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354983$13D1F604-415B-47D1-B049-57F844493B99","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1e22c5b89240190fc74b760088a55141cf0fb60b","datavalue":{"value":{"entity-type":"item","numeric-id":180135,"id":"Q180135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354983$5C9594DD-7601-4CB8-B711-E72F435DBB2F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8e396f0dbd52eaba8fc73bd5cae8304e6cc66a22","datavalue":{"value":{"time":"+2015-07-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2354983$7730E314-053C-4698-BF7D-606EF168C81F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"73f4ebce8a8cdf86a731723c395725c55678baff","datavalue":{"value":"https://arxiv.org/abs/1311.7283","type":"string"},"datatype":"url"},"type":"statement","id":"Q2354983$8AB27E3D-840B-4359-8251-B6ABFCA57477","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9bc500c5b0954e718f066e5684b49fae2c79d1bf","datavalue":{"value":"The paper is devoted to questions of algebraic topology related with the theory of distributive computing. \\textit{M. Herlihy} and \\textit{N. Shavit} [J. ACM 46, No. 6, 858--923 (1999; Zbl 1161.68469)] gave necessary and sufficient combinatorial conditions characterizing the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by reading and writing a shared memory. They introduced a formalism for tasks in which a task's possible input and output values each are associated with simplicial complexes. This allowed them to characterize computability in terms of the topological properties of the simplicial complexes. A distributed protocol solves the given task if it yields a correct output for any input simplex and any possible execution. It has been realized that it is fruitful to summarize the totality of all possible executions as a single simplicial complex, the \\textit{protocol complex}. A crucial construction in understanding the topology of the broad class of protocol complexes for \\(n+1\\) processes is the \\textit{standard chromatic subdivision} \\(\\chi(\\Delta^n)\\) [\\textit{M. Herlihy} et al., Distributed computing through combinatorial topology. Amsterdam: Elsevier/Morgan Kaufmann (2014; Zbl 1341.68004)].  The author of the paper under review studies the analog of this construction, which is derived from the snapshot model.  For any integer \\(n\\geq 0\\), denote \\([n]=\\{0, \\ldots, n\\}\\). Let \\(n\\geq 1\\) be a natural number. An \\textit{\\(n\\)-view} is a \\(2\\times t\\)-matrix  \\[  W= \\left( \\begin{matrix} V_1 & \\ldots & V_{t-1} & [n]\\\\ I_1 & \\ldots & I_{t-1} & I_t \\end{matrix} \\right),  \\]  where \\(t\\geq 1\\), such that the following properties are satisfied: {\\parindent=6mm \\begin{itemize} \\item[(1)] \\(\\emptyset\\not=V_1\\subset \\cdots \\subset V_{t-1}\\subset [n]\\); \\item [(2)] the sets \\(I_1, \\ldots, I_t\\) are disjoint; \\item [(3)] \\(\\emptyset\\not=I_k\\subseteq V_k\\), for \\(k=1, \\ldots, t-1\\).   \\end{itemize}} The convention \\(V_t=[n]\\) is used. The \\textit{dimension} of the \\(n\\)-view \\(W\\) is defined by \\(dim W= |I_1|+ \\cdots + |I_t|-1\\).  A \\textit{local view} \\(L=(V,x)\\) is a pair where \\(V\\subseteq [n]\\) and \\(x\\in V\\). The local view \\(L=(V,x)\\) \\textit{belongs to} \\(W\\), writing \\(L\\in W\\), if there exists \\(1\\leq k\\leq t\\), such that \\(V=V_k\\) and \\(x\\in I_k\\). Let \\(V(W)\\) denote the set of all local views belonging to \\(W\\). Clearly, \\(|V(W)|=dim W +1\\).  In the paper under review, an \\textit{abstract simplicial complex} \\(K\\) is defined as a set of subsets of a finite set \\(S\\) such that {\\parindent=6mm \\begin{itemize} \\item[{\\(\\bullet\\)}] \\(\\{x\\}\\in K\\) for all \\(x\\in S\\); \\item [{\\(\\bullet\\)}] if \\(\\tau\\subset \\sigma\\), and \\(\\sigma\\in K\\), then \\(\\tau\\in K\\).   \\end{itemize}} The set \\(S\\) is called the \\textit{vertex set} of \\(K\\). Each \\(\\sigma\\in K\\) is called a \\textit{face}. The abstract simplicial complex \\(K=2^S\\) consisting of all subsets \\(\\sigma\\subseteq S\\) is called the \\textit{simplex}.  For any natural \\(n\\), a simplicial complex \\(View^n\\) is defined as follows: {\\parindent=6mm \\begin{itemize} \\item[{\\(\\bullet\\)}] the set of of vertices is the set of all local views  \\[  V(View^n)= \\{(V,x)| x\\in V\\subseteq [n]\\};  \\]  \\item [{\\(\\bullet\\)}] a subset \\(S\\subseteq V(View^n)\\) forms a simplex if and only if \\(S=V(W)\\) for some \\(n\\)-view W.   \\end{itemize}} The \\(n\\)-views are identified with the corresponding simplices of \\(View^n\\).  { Definition 3.6.} Assume \\(n\\) is a natural number. {\\parindent=6mm \\begin{itemize} \\item[(1)] We call an \\(n\\)-view  \\[  W= \\left( \\begin{matrix} V_1 & \\ldots & V_{t-1} & [n]\\\\ I_1 & \\ldots & I_{t-1} & I_t \\end{matrix} \\right)  \\]  an \\textit{immediate snapshot view} if we have \\(I_k\\subseteq V_k\\setminus V_{k-1}\\) for all \\(k= 2, \\ldots,t\\). \\item [(2)] If \\(W\\) is an immediate snapshot view and \\(U\\subset W\\), the \\(U\\) is also an immediate snapshot view. Therefore the immediate snapshot views form a simplicial subcomplex of \\(View^n\\), which we denote by \\(\\chi(\\Delta^n)\\).   \\end{itemize}} The simplicial complexes \\(View^n\\) and \\(\\chi(\\Delta^n)\\) are equipped with a canonical simplicial action of the permutation group \\(\\mathcal{S}_{[n]}\\). This is the reflection of the fact that the considered protocols are symmetric with respect to the renaming of processors.  Let \\(K\\) be an abstract simplicial complex. The set \\(\\mathcal{F}(K)\\) of all its simplices is partially ordered by inclusion. It is called the \\textit{face poset} of \\(K\\). For \\(\\sigma\\in K\\), denote by \\(\\mathcal{F}(K)_{\\geq\\sigma}\\) the set \\(\\{\\tau\\in K| \\sigma \\subseteq \\tau\\}\\) ordered by inclusion.  Denote by \\(\\mathcal{B}_t\\) the partially ordered set of all subsets of a set with \\(t\\) elements. A simplex \\(\\sigma\\in K\\) is \\textit{free} if \\(\\mathcal{F}(K)_{\\geq\\sigma}\\cong \\mathcal{B}_t\\) for some \\(t\\geq 1\\).  For a free simplex \\(\\sigma\\), a \\textit{collapse} of \\(K\\) associated to \\(\\sigma\\) is the process of deleting from \\(K\\) all the simplices in \\(\\mathcal{F}(K)_{\\geq\\sigma}\\).  When \\(M\\) is a subcomplex of \\(K\\), we say that \\(K\\) is \\textit{collapsible to} \\(M\\) if there exists a sequence of collapses leading from \\(K\\) to \\(M\\). We say that \\(K\\) is \\textit{collapsible} if it is collapsible to the void simplicial complex.  {Definition 4.1.} Assume \\(K\\) is an abstract simplicial complex with a simplicial action of a finite group \\(G\\). {\\parindent=6mm \\begin{itemize} \\item[(a)] A simplex \\(\\sigma\\) is called \\textit{\\(G\\)-free} if it is free, and for all \\(g\\in G\\), such that \\(g(\\sigma)\\not=\\sigma\\), we have  \\[  \\mathcal{F}_{\\geq{\\sigma}}\\cap \\mathcal{F}_{\\geq{g(\\sigma)}}= \\emptyset.  \\]  \\item [(b)] If \\(\\sigma\\) is \\(G\\)-free, we call the procedure of deleting all the simplices from the union \\(\\bigcup_{g\\in G}\\mathcal{F}(K)_{\\geq g(\\sigma)}\\) the \\textit{\\(G\\)-collapse} of \\(K\\).   \\end{itemize}} { Theorem 4.4.} For every natural number \\(n\\), the following statements are true. {\\parindent=6mm \\begin{itemize} \\item[(1)] The simplicial complex \\(View^n\\) is \\(\\mathcal{S}_{[n]}\\)-collapsible to \\(\\chi(\\Delta^n)\\). \\item [(2)] The simplicial complex \\(\\chi(\\Delta^n)\\) is \\(\\mathcal{S}_{[n]}\\)-collapsible.   \\end{itemize}} From Theorem 4.4 follows the statement that \\(\\chi(\\Delta^n)\\) is collapsible. Even this statement is new.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$F971BB99-4FAD-48AF-993D-2FD7A8B60869","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1722e8eaf8d0b6e989e3d4620a85df21f8eb2337","datavalue":{"value":"55U10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$5FD77671-9AFD-4669-9491-A86534BCFFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b8f412c62952107f7ff74e77578c2ab25d3e121a","datavalue":{"value":"68Q85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$DF8C1FC4-CAB2-46F4-9ADA-15FF13EB9781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cd55e37faed400f27c01e5bfb5d6bb41ead1f10","datavalue":{"value":"57Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$29EE1A01-CE78-4C94-89FF-589502F4FA64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"de616e6d720c09473dae9a266341e29be3f94ea4","datavalue":{"value":"6465448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$50FADDDC-921E-49B3-BB49-94121CB17DC6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78b826843ab20a87c9262e0d558d414868bdd4a5","datavalue":{"value":"simplicial complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$51109092-070C-4692-9175-599741C72EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7857e3a9ba73ed192fa9df4aeb129c2ae7af0262","datavalue":{"value":"view complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$1F968C8E-3FE8-4621-919C-EAEAED656251","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"39c031cbb42db6444c6df1d75a355e569bf793f8","datavalue":{"value":"collapses","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$43F28F31-271D-4E8E-86DB-83B8606557A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b36d924addd0d2f364b26835d91730b673a9f92","datavalue":{"value":"distributed computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$B8240DAD-EAD5-4910-AF7C-D2C0EA1E0FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a4918a1bd2921ad3251697d093880c02b3a9f1a","datavalue":{"value":"immediate anapshot","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$B8744756-D790-4905-A766-6A543F8F6BA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d295e4b0412d550655f45497352d44e697faabb4","datavalue":{"value":"read-write protocols","type":"string"},"datatype":"string"},"type":"statement","id":"Q2354983$20D45A23-890E-4A5E-818D-47FC90AD1662","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"16c26e4ac190a2cc8301d13290ef2f97e240c6b3","datavalue":{"value":{"entity-type":"item","numeric-id":590338,"id":"Q590338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2354983$3BBA631F-C368-46EB-9198-6C1EE058F53C","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":"Q2354983$67EE9244-4278-4BA9-94F0-696F02858F2C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fceaf6d310326fd8ec514e3acbc5cd9f5c040dfa","datavalue":{"value":"W2963052734","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$D48822B4-154D-4F94-A07E-C44DA30B78B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1cb8acb27c9f9ab5bc260dbc45b1286b0c0f79a","datavalue":{"value":"10.4310/HHA.2015.V17.N1.A15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2354983$C85451DF-5E73-46CC-9A5A-61F760205081","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93391c1c2f5c6a7a46d3e0d1a8a1e923d7e22dfa","datavalue":{"value":{"entity-type":"item","numeric-id":471457,"id":"Q471457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfbf84fd222a92f105b2fedb0f57d6b0f20a14a6","datavalue":{"value":{"amount":"+0.8393299579620361","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":"Q2354983$203D4866-BEE7-4340-BE2D-54911B8BB414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f000e73eaf3e7a3a6e83a9e698522672e05fb9ab","datavalue":{"value":{"entity-type":"item","numeric-id":1935105,"id":"Q1935105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c96f54e3a3f5aff176fbe156f955bd40cdf09e9a","datavalue":{"value":{"amount":"+0.8262627720832825","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":"Q2354983$51D37DA8-DEB7-4282-92A3-1C10AAFD62C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a875932073a9c1ad400c5457e82dda68752c52b","datavalue":{"value":{"entity-type":"item","numeric-id":2802937,"id":"Q2802937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68179e03dd96f838b892baeb5ef7741fe0eb0a68","datavalue":{"value":{"amount":"+0.8172418475151062","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":"Q2354983$2162DF16-287C-41C6-905F-11786B14475B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90824894029653e9f2f338f674cb0169d8d45710","datavalue":{"value":{"entity-type":"item","numeric-id":1616395,"id":"Q1616395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c01103430a1ef875afebb58ee287431fe6b44e06","datavalue":{"value":{"amount":"+0.8119537234306335","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":"Q2354983$51698609-FF40-4D49-B918-DD0F7788823E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f2caf0b57f6a50529c585ed70dd2f66e9e95eef","datavalue":{"value":{"entity-type":"item","numeric-id":4560213,"id":"Q4560213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07ba7dc7dbb4362f16466b880145169ebdddc9aa","datavalue":{"value":{"amount":"+0.8110344409942627","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":"Q2354983$744FD5EA-E28A-4B9C-B1DB-DA00421D136F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2354983","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2354983"}}}}}