Content deleted Content added
→Formal definition: t_j is subset of indices not a subset of variables. The order of the product of domains matters and was ambiguous. An alternative is to go back to the Russell's definition<ref name=Russell2010> which defines t_j as a tuple of variables instead of indices to enforce order. |
Citation bot (talk | contribs) Added pages. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 142/579 |
||
Line 49:
* all first-order reducts of the [[Rado graph|countable random graph]],<ref>{{Cite book |last1=Bodirsky |first1=Manuel |title=Proceedings of the 43rd Annual Symposium on Theory of Computing (STOC '11) |title-link=Symposium on Theory of Computing |last2=Pinsker |first2=Michael |publisher=[[Association for Computing Machinery]] |year=2011 |isbn=978-1-4503-0691-1 |pages=655–664 |contribution=Schaefer's theorem for graphs |doi=10.1145/1993636.1993724 |arxiv=1011.2894 |s2cid=47097319}}</ref>
* all first-order reducts of the [[model companion]] of the class of all C-relations,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Jonsson |first2=Peter |last3=Pham |first3=Trung Van |date=2017-08-02 |title=The Complexity of Phylogeny Constraint Satisfaction Problems |url=https://doi.org/10.1145/3105907 |journal=ACM Trans. Comput. Logic |volume=18 |issue=3 |pages=23:1–23:42 |doi=10.1145/3105907 |arxiv=1503.07310 |issn=1529-3785}}</ref>
* all first-order reducts of the universal homogenous [[Partially ordered set|poset]],<ref>{{Cite journal |last1=Kompatscher |first1=Michael |last2=Pham |first2=Trung Van |date=2017 |title=A Complexity Dichotomy for Poset Constraint Satisfaction |journal=DROPS-IDN/V2/Document/10.4230/LIPIcs.STACS.2017.47 |pages=47:1–47:12 |language=en |publisher=Schloss Dagstuhl – Leibniz-Zentrum für Informatik |doi=10.4230/LIPIcs.STACS.2017.47|doi-access=free }}</ref>
* all first-order reducts of homogenous undirected graphs,<ref>{{Cite journal |last1=Bodirsky |first1=Manuel |last2=Martin |first2=Barnaby |last3=Pinsker |first3=Michael |last4=Pongrácz |first4=András |date=January 2019 |title=Constraint Satisfaction Problems for Reducts of Homogeneous Graphs |url=https://epubs.siam.org/doi/10.1137/16M1082974 |journal=SIAM Journal on Computing |language=en |volume=48 |issue=4 |pages=1224–1264 |doi=10.1137/16M1082974 |issn=0097-5397|arxiv=1602.05819 }}</ref>
* all first-order reducts of all unary structures,<ref>{{Citation |last1=Bodirsky |first1=Manuel |title=A Dichotomy for First-Order Reducts of Unary Structures |date=2018-05-20 |doi=10.23638/LMCS-14(2:13)2018 |last2=Mottet |first2=Antoine|journal=Logical Methods in Computer Science |volume=14 |issue=2 |arxiv=1601.04520 }}</ref>
| |||