{"entities":{"Q681598":{"pageid":683447,"ns":120,"title":"Item:Q681598","lastrevid":63550629,"modified":"2026-04-11T13:55:28Z","type":"item","id":"Q681598","labels":{"en":{"language":"en","value":"Regular families of forests, antichains and duality pairs of relational structures"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6837304"}},"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":"Q681598$8EED9249-4B29-4E45-8BD0-CEAF89D22F9B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ad7de1e53c7413cfae63c7bb0100b4bc8d780604","datavalue":{"value":{"text":"Regular families of forests, antichains and duality pairs of relational structures","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q681598$DC5A8CB3-2104-4825-B24B-70656CB4F4E4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"89a59d621ea264ef6aeaefab00d5f07d20dd693f","datavalue":{"value":"1399.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$A67FD298-BBA4-4EA4-BDE6-8799107ACDB9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dbe5f99d1b91051e96804c11a86bf85ab75e8c10","datavalue":{"value":{"entity-type":"item","numeric-id":284346,"id":"Q284346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$F308A477-A902-4EEE-85A7-2686D9E1E38C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c7c9b7f3b89b99b89c913783f5d2f1bc0d401a64","datavalue":{"value":{"entity-type":"item","numeric-id":681597,"id":"Q681597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$DD1A8733-0B5C-4A20-A408-C747262881AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfb4a17abdcf37f7572da8c995af52b66fc8d692","datavalue":{"value":{"entity-type":"item","numeric-id":168595,"id":"Q168595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$71F6E7AB-E752-4A81-AA20-68A2A25D3DF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b98fce2ef81dbe6df6389a7622d9c9855a79da5","datavalue":{"value":{"entity-type":"item","numeric-id":200913,"id":"Q200913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$3FF089AA-333A-4CF1-934F-069599FE7892","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$B2EDD765-EFBF-445D-87F4-7DCF5FDA22E5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"37dc8ae22dcec2d49b93f95859fca43d86658768","datavalue":{"value":{"time":"+2018-02-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q681598$8020A17A-FEB9-4299-8F4B-457EA931FBF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae8ff0f3f118de467a431e263bcb7853d8478113","datavalue":{"value":"https://arxiv.org/abs/1207.4402","type":"string"},"datatype":"url"},"type":"statement","id":"Q681598$62A8CF27-2E6F-45A4-A2AE-218AC0DBE5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c06943a786808bafe30dea836140feceed45071a","datavalue":{"value":"http://real.mtak.hu/44134/1/1207.4402v3.pdf","type":"string"},"datatype":"url"},"type":"statement","id":"Q681598$4C5599E6-1F61-4B7D-B0D6-8A0ADE072C2C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6b49a00e6f7ec0c1d750462844ba95a0c1b27f35","datavalue":{"value":"Given a relational type \\(\\sigma = \\{ R_1, \\ldots, R_m \\}\\), and a \\(\\sigma\\)-structure \\(\\mathbb A = \\langle A;\\) \\(R_1(\\mathbb A), \\ldots,\\) \\(R_m(\\mathbb A) \\rangle\\), where \\(R_i(\\mathbb A) \\subseteq A^{r_i}\\) for each \\(i\\), the \\textit{incidence graph} Inc(\\(\\mathbb A\\)) is the bipartite graph of vertices \\(A \\cup C\\) (where \\(C = \\{ (R_i, x_1, \\ldots, x_{r_i}) : R_i(\\mathbb A)(x_1, \\ldots, x_{r_i}) \\}\\)) and edges \\(\\{x_j, (R_i, x_1, \\ldots, x_{r_i})\\}\\) for each \\(i\\), \\(j\\) and \\((R_i, x_1,\\) \\(\\ldots, x_{r_i}) \\in C\\). This article concerns those \\(\\mathbb A\\) for which Inc(\\(\\mathbb A\\)) is acyclic: fixing \\(\\sigma\\), let \\(\\mathbb F\\) be the set of \\(\\sigma\\)-structures for which the incidence graph is a forest, and call the structures in \\(\\mathbb F\\) \\textit{\\(\\sigma\\)-forests}.  For two \\(\\sigma\\)-forests \\(\\mathbb A\\) and \\(\\mathbb B\\), write ``\\(\\mathbb A \\to \\mathbb B\\)'' if there is a homomorphism from \\(\\mathbb A\\) to \\(\\mathbb B\\). Notice that \\(\\to\\) is a preorder, i.e., a reflexive and transitive relation. Much of this article concerns the family of \\(\\sigma\\)-forests and homomorphisms, although there is little explicit category theory (and this article is relatively self-contained). For example, a \\textit{core} of a \\(\\sigma\\)-forest \\(\\mathbb A\\) is a \\(\\sigma\\)-forest \\(\\mathbb B\\) of minimum cardinality such that \\(\\mathbb A \\leftrightarrow \\mathbb B\\); a core of a \\(\\sigma\\)-forest is unique up to isomorphism. Much of this paper is devoted to ``duality pairs'': we call \\((\\mathcal O, \\mathcal D)\\) a \\textit{duality pair} if, for any \\(\\sigma\\)-forest \\(\\mathbb A\\), \\(\\mathbb A \\to \\mathbb D\\) for some \\(\\mathbb D \\in \\mathcal D\\) if and only if for all \\(\\mathbb T \\in \\mathcal O\\), \\(\\mathbb T \\not \\to \\mathbb A\\).  We are interested in ``regular'' families \\(\\mathcal O \\subseteq \\mathbb F\\). For any \\(\\sigma\\)-structure \\(\\mathbb A\\) and any \\(a \\in A\\), we obtain a ``rooted structure'' \\((\\mathbb A, a)\\), and given any two rooted structures \\((\\mathbb A, a)\\) and \\((\\mathbb B, b)\\), we may ``add'' them by identifying their roots, obtaining \\([(\\mathbb A, a) + (\\mathbb B, b)]\\). Notice that if both \\(\\mathbb A\\) and \\(\\mathbb B\\) were \\(\\sigma\\)-forests, then so is their sum. Let  \\[  {\\mathcal O} - (\\mathbb A, a) = \\{(\\mathbb B, b) : [(\\mathbb A, a) + (\\mathbb B, b)] \\in \\mathcal O \\}.  \\]  Write \\((\\mathbb A, a) \\; {\\sim}_{\\mathcal O} \\; (\\mathbb A', a')\\) if \\({\\mathcal O} - (\\mathbb A, a) = {\\mathcal O} - (\\mathbb A', a')\\). Then ``in the spirit of the Myhill-Nerode theorem,'' we may define \\(\\mathcal O\\) to be \\textit{regular} if \\({\\sim}_{\\mathcal O}\\) has finitely many equivalence classes.  Much machinery (much of it using duality pairs) is assembled in the first half of the article, and having assembled the machinery, the second half of the article is devoted to the following result.  If \\(\\mathcal O\\) is a regular set of \\(\\sigma\\)-forests, then the set of cores of the \\(\\to\\)-minimal elements of \\(\\mathcal O\\) is also regular.  The motivation is provided by the Constraint Satisfaction Problem, but the machinery may also be of interest to algebraists.","type":"string"},"datatype":"string"},"type":"statement","id":"Q681598$7B4F3F1F-FE79-45A1-B0F1-ED20B33516DF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f4c2e453a383fe1e064f27e4ca3ff49f8a1646b9","datavalue":{"value":{"entity-type":"item","numeric-id":587174,"id":"Q587174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$33DB1D35-2147-4730-AA11-A124ABCBDEAE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$EF7D5D6F-C3FF-41F7-AFE5-08757F5704FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$74F38E4D-D0F2-40DB-A732-689722B170DD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"69bd73eca0246c99a1fabf985ea8863acebdb461","datavalue":{"value":"6837304","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$A9CDF1CD-3DD7-428C-B42C-E8EEF92549A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab1b2d33963dc85c015ba353e197645da8b8601d","datavalue":{"value":"forests","type":"string"},"datatype":"string"},"type":"statement","id":"Q681598$56BD2362-73CB-4A61-B9C8-6C9D3C4F35FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"922c01258e140214b68568956989c4ba97b3c6f4","datavalue":{"value":"antichains","type":"string"},"datatype":"string"},"type":"statement","id":"Q681598$7E1C3C43-A6C4-4986-9F58-41E2664A3CFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d51c626d0d8f96f9f931ac62a34ddc944db0fca2","datavalue":{"value":"duality pairs","type":"string"},"datatype":"string"},"type":"statement","id":"Q681598$4EE0514C-A5AE-4CAA-96CF-6B01324CD32C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb45a366c5f73694d4193741149731f4b28dce52","datavalue":{"value":"relational structures","type":"string"},"datatype":"string"},"type":"statement","id":"Q681598$D90FE9AA-D7B9-4EB2-88E2-55079713519E","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":"Q681598$E9BE12D2-6514-48AD-A8D6-CD59228578D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"269c2ea950581bcd5e2b90ecbc6f76cc928ba67a","datavalue":{"value":"W1924742230","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$798893A9-FD29-42E0-AD48-F6C3318CC1F9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24684c0a71333143c5052668f8ab73b1174c38e7","datavalue":{"value":{"entity-type":"item","numeric-id":5504701,"id":"Q5504701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$04450BD1-0759-4B9E-8E3C-7DFF3FEE44DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b525cdf69267763822538deb49093584b5ad4ba","datavalue":{"value":{"entity-type":"item","numeric-id":2460618,"id":"Q2460618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$F204102F-4B4D-4851-AB88-16B5C79C395E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cecbc5cd7a91f5abc1feda95b756c74ca8f2f750","datavalue":{"value":{"entity-type":"item","numeric-id":603883,"id":"Q603883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$A5E1DC2E-F3B3-4D3B-A89E-17BAEA22B150","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da5c6061c3f6daf7454d0e9c58daef6f441530aa","datavalue":{"value":{"entity-type":"item","numeric-id":4210136,"id":"Q4210136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$0A5796CD-CA6F-4CA8-B381-B1F8B2FFEC28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9120165a90f157001c3ebf286baf21899fd769f7","datavalue":{"value":{"entity-type":"item","numeric-id":2427538,"id":"Q2427538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$99DDF639-B89B-4AB9-83F6-ACF94E500B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"561871863e7516f8e3a24736861cad5669c3b1ce","datavalue":{"value":{"entity-type":"item","numeric-id":5453499,"id":"Q5453499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$0B82AF62-28B3-4F3B-8269-D09FB8A1CA7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"610aae95183384a106db247ebacea87082ad9f54","datavalue":{"value":{"entity-type":"item","numeric-id":5716799,"id":"Q5716799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$75BE6E6A-313B-47FD-B0CC-574C962DF866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15f0d5d06eb8f30a0d71ed29f48211a4f9dca39","datavalue":{"value":{"entity-type":"item","numeric-id":1850486,"id":"Q1850486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$EF8E2D77-D50D-4E3B-9786-C961EAF1B524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31ffb594742705f0bb995ca7f67a18307c6b90a4","datavalue":{"value":{"entity-type":"item","numeric-id":5470800,"id":"Q5470800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q681598$1F7C9729-5CA4-4235-8A32-7B01453E6143","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42704d824072c3e613a7fcdd57d494110a521a39","datavalue":{"value":"10.1007/S00493-015-3003-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q681598$71A6BEE5-062D-45AB-A340-5F5886B2574C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a29a7615b2ae0931f791efc5fb6c6cfd6c34e96","datavalue":{"value":{"entity-type":"item","numeric-id":5213570,"id":"Q5213570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"399236e14ed391e716ac4d5726dc75d909f45214","datavalue":{"value":{"amount":"+0.769963800907135","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":"Q681598$4B9BF0FE-3977-4D1D-BE38-53D6056E165C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9b78b85fed9e6b032c58760bc2e1ac83eba3830","datavalue":{"value":{"entity-type":"item","numeric-id":382885,"id":"Q382885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72feb617f2fa7a2993448a869ca624db094f54e9","datavalue":{"value":{"amount":"+0.7585995197296143","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":"Q681598$0719974B-03BF-4D4E-BC27-4ED7511AC5BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ae14bc13c2ae3c20f5df6f6dcaac55db946873c","datavalue":{"value":{"entity-type":"item","numeric-id":2427538,"id":"Q2427538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7a6c0ee6363581be2d6746634ef58976b349a6f2","datavalue":{"value":{"amount":"+0.7470804452896118","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":"Q681598$139AEABE-6DE3-49DD-AA64-190DF09E989F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf173d84dc3e617f6eee4f1e8d90c45a7dedcdd7","datavalue":{"value":{"entity-type":"item","numeric-id":2870506,"id":"Q2870506"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"512efba2c9b3434dc521a3374df3ef1aa09496db","datavalue":{"value":{"amount":"+0.7182369232177734","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":"Q681598$AB0F6519-8627-49FD-BD04-656FFBB50414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f072ca5aedcce07b13b699e7c4c00a4483148d00","datavalue":{"value":{"entity-type":"item","numeric-id":3586031,"id":"Q3586031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb00700f07ce73f441e51ae106e1df1c2ba9e178","datavalue":{"value":{"amount":"+0.7118039131164551","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":"Q681598$3FBF908C-D00F-420D-B0E7-CB0B1272B88E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regular families of forests, antichains and duality pairs of relational structures","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regular_families_of_forests,_antichains_and_duality_pairs_of_relational_structures"}}}}}