On the enumeration of Tarski fixed points

Julian M\"uller

arxiv: 2308.07923 · v2 · submitted 2023-08-15 · 💻 cs.DM · cs.CC

On the enumeration of Tarski fixed points

Julian M\"uller This is my paper

Pith reviewed 2026-05-24 07:50 UTC · model grok-4.3

classification 💻 cs.DM cs.CC

keywords Tarski fixed pointsisotone mapsenumerationquery complexitylattice widthbinary relationsbisimulations

0 comments

The pith

Enumerating Tarski fixed points of isotone maps requires as many queries as the lattice width in the worst case.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper derives query complexity lower bounds showing that any deterministic or bounded-error algorithm for finding three or more Tarski fixed points must perform asymptotically as many queries as the width of the lattice when the map is isotone. This bound is exponential on the lattice of binary relations and similar structures. It also presents depth-first and flashlight search algorithms that enumerate fixed points of increasing or decreasing isotone maps in polynomial space on polynomial-height lattices. These algorithms achieve polynomial delay on the lattices of binary relations, quasiorders, and equivalences when the problem avoids NP-hardness or exponential query bounds, including an O(n^3 m) delay method for listing bisimulations.

Core claim

For isotone maps the query complexity of enumerating Tarski fixed points is at least the lattice width, which grows exponentially on lattices such as binary relations. For the subclasses of increasing and decreasing isotone maps, the depth-first and flashlight search procedures enumerate all fixed points using only polynomial space on any polynomial-height lattice and run with polynomial delay on the lattices of binary relations, quasiorders and equivalences whenever the underlying decision problem is neither NP-hard nor subject to an exponential query lower bound.

What carries the argument

Lattice width as the query lower bound for isotone maps together with depth-first search and flashlight search procedures restricted to increasing or decreasing maps.

If this is right

On the lattice of binary relations any algorithm for general isotone maps must use exponentially many queries in the worst case.
The two search algorithms run in polynomial space when applied to the lattices of binary relations, quasiorders and equivalences.
Bisimulations on a transition system with n states and m transitions can be listed with O(n^3 m) delay.
Polynomial-delay enumeration is possible on these lattices precisely when finding three or more fixed points is neither NP-hard nor subject to an exponential query lower bound.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same width-based query lower bound may limit enumeration algorithms for other order-theoretic fixed-point problems.
The separation between isotone, increasing and decreasing maps offers a template for designing space-efficient procedures in related verification tasks.
The polynomial-delay results could extend to additional behavioral equivalences once suitable height and monotonicity conditions are identified.
Lattices with sub-polynomial height might admit even faster enumeration under the same algorithmic framework.

Load-bearing premise

The polynomial-space enumeration algorithms work only when restricted to increasing or decreasing isotone maps on lattices of polynomial height.

What would settle it

Discovery of a deterministic or bounded-error algorithm that enumerates three or more Tarski fixed points of an isotone map while using fewer than the lattice width queries on some input would falsify the lower bound.

Figures

Figures reproduced from arXiv: 2308.07923 by Julian M\"uller.

read the original abstract

We study the problem of enumerating Tarski fixed points on finite lattices. We derive query complexity lower bounds for finding three or more Tarski fixed points of isotone maps and the subclasses of increasing and decreasing isotone maps. Specifically, we show that any deterministic or bounded-error algorithm must perform asymptotically as many queries in the worst case as the lattice width for isotone maps, which is exponential for the lattice of binary relations and other relevant lattices. We also present two enumeration algorithms for fixed points of increasing or decreasing isotone maps based on depth-first and flashlight search. Both algorithms run in polynomial space on polynomial-height lattices, but are particularly suitable in terms of applicability and runtime performance on different lattices, as they build on differing properties of the underlying lattice. Finally, we discuss the enumeration of Tarski fixed points on the lattices of binary relations, quasiorders and equivalences, demonstrating that the presented algorithms run in polynomial space on these lattices and perform with polynomial delay whenever the problem of finding three or more fixed points is neither NP-hard nor has an exponential query lower bound. We exemplify how these results can be used to list instances of various models of behavioral or role equivalence, specifically deriving a polynomial-space algorithm that enumerates bisimulations with $\mathcal O(n^3m)$ delay on a transition system with $n$ states and $m$ transitions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives exponential query lower bounds for listing three-plus Tarski fixed points of isotone maps on wide lattices and supplies two search algorithms that work in polynomial space for the increasing or decreasing subclasses, with a worked example on bisimulation enumeration.

read the letter

The core contribution is a query lower bound showing that any deterministic or bounded-error algorithm needs asymptotically as many queries as the lattice width to find three or more fixed points of an isotone map; this is exponential on the lattice of binary relations. The paper also gives two concrete enumeration procedures, depth-first search and flashlight search, that apply only to increasing or decreasing isotone maps and run in polynomial space when the lattice has polynomial height. On the lattices of binary relations, quasiorders, and equivalences these procedures stay in polynomial space and achieve polynomial delay precisely when the lower bound does not force exponential work and the problem is not NP-hard. The bisimulation application then yields an explicit O(n³m)-delay enumerator on an n-state, m-transition system. That separation between the general isotone case and the tractable subclasses is the clearest new piece. The lower bound is stated directly in terms of width and the algorithms are built from standard search primitives, so the claims line up without obvious circularity. The application to behavioral equivalences is carried through to a concrete delay bound, which is more than most order-theoretic papers deliver. The main limitation is that the algorithms do not apply to arbitrary isotone maps, so they sit beside rather than contradict the lower bound. Polynomial delay is also conditional on the problem not being hard, which is accurate but narrows the scope. Without the full proofs it is impossible to check every derivation step, but the abstract maintains the necessary distinctions and the stress-test found no load-bearing gap. This is for people who work on enumeration complexity in lattices or on fixed-point algorithms for verification. A reader who needs either the query bound or a practical way to list bisimulations will find usable material. It is worth sending to referees because the results are specific, the application is explicit, and the distinctions are kept straight.

Referee Report

0 major / 2 minor

Summary. The paper studies enumeration of Tarski fixed points on finite lattices. It establishes query-complexity lower bounds showing that any deterministic or bounded-error algorithm for finding three or more fixed points of an isotone map must perform asymptotically as many queries as the lattice width in the worst case (exponential for the lattice of binary relations). It presents two enumeration algorithms (depth-first search and flashlight search) for the subclasses of increasing and decreasing isotone maps; both run in polynomial space on polynomial-height lattices. The paper then specializes the results to the lattices of binary relations, quasiorders and equivalences, and derives a polynomial-space algorithm that enumerates bisimulations with O(n³m) delay on a transition system with n states and m transitions.

Significance. If the lower-bound arguments and algorithm analyses hold, the work supplies tight query lower bounds that separate the general isotone case from the increasing/decreasing subclasses and supplies concrete polynomial-space, polynomial-delay procedures for several lattices of combinatorial interest. The explicit connection to enumeration of behavioral equivalences (bisimulations) gives the results immediate applicability in concurrency theory.

minor comments (2)

[abstract / introduction] The abstract states that the algorithms 'run in polynomial space on polynomial-height lattices' and achieve 'polynomial delay whenever the problem of finding three or more fixed points is neither NP-hard nor has an exponential query lower bound.' A short clarifying sentence in the introduction or §4 would help the reader see exactly which theorem or corollary justifies the polynomial-delay claim for the binary-relation lattice.
[application to bisimulations] The O(n³m) delay bound for bisimulation enumeration is stated without an explicit reference to the underlying lattice height or width calculation that makes the flashlight-search variant polynomial-delay on this instance; adding a one-sentence pointer to the relevant lemma would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of the query lower bounds and the polynomial-space algorithms, and the recommendation of minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central claims separate query lower bounds (tied to lattice width for isotone maps) from constructive enumeration algorithms (depth-first and flashlight search restricted to increasing/decreasing maps on polynomial-height lattices). These are presented as independent results without any reduction of a 'prediction' to a fitted parameter, self-definition of a quantity in terms of itself, or load-bearing reliance on self-citations that themselves reduce to the target claim. The distinction between exponential lower bounds on general lattices and polynomial-space algorithms on restricted cases is maintained explicitly, with no equations or steps that equate outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard order theory (finite lattices, isotone maps) and complexity notions (query complexity, polynomial space) without introducing new free parameters, ad-hoc axioms, or invented entities.

axioms (2)

standard math Finite lattices possess a well-defined width and height.
Invoked for the query lower bound and the polynomial-space claim on polynomial-height lattices.
domain assumption Isotone maps are order-preserving functions on the lattice.
Central to the definition of Tarski fixed points and the distinction between increasing and decreasing subclasses.

pith-pipeline@v0.9.0 · 5765 in / 1372 out tokens · 50359 ms · 2026-05-24T07:50:56.772675+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

[2]

Bard Bloom, Sorin Istrail, and Albert R. Meyer. Bisimulation can’t be traced. Journal of the ACM, 42(1):232–268, January 1995. doi:10.1145/200836.200876

work page doi:10.1145/200836.200876 1995
[3]

Transformational design and implementation of a new efficient solution to the ready simulation problem

Bard Bloom and Robert Paige. Transformational design and implementation of a new efficient solution to the ready simulation problem. Science of Computer Programming , 24(3):189–220, 1995. doi:10.1016/0167-6423(95)00003-B

work page doi:10.1016/0167-6423(95)00003-b 1995
[4]

Borgatti, John P

Stephen P. Borgatti, John P. Boyd, and Martin G. Everett. Iterated roles: Mathematics and application. Social Networks, 11(2):159–172, 1989. doi:10.1016/0378-8733(89)90010-5

work page doi:10.1016/0378-8733(89)90010-5 1989
[5]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. The class of all regular equivalences: Al- gebraic structure and computation. Social Networks, 11(1):65–88, 1989. doi:10.1016/ 0378-8733(89)90018-X

work page 1989
[6]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. Graph colorings and power in experimental exchange networks. Social Networks, 14(3-4):287–308, 1992. doi:10.1016/0378-8733(92) 90006-S

work page doi:10.1016/0378-8733(92 1992
[7]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. Ecological and perfect colorings. Social Networks, 16(1):43–55, 1994. doi:10.1016/0378-8733(94)90010-8

work page doi:10.1016/0378-8733(94)90010-8 1994
[8]

Boyd and Martin G

John P. Boyd and Martin G. Everett. Relations, residuals, regular interiors, and relative regular equivalence. Social Networks, 21(2):147–165, 1999. doi:10.1016/S0378-8733(99) 00006-4

work page doi:10.1016/s0378-8733(99 1999
[9]

Social positions and simulation relations

Joel Brynielsson, Lisa Kaati, and Pontus Svenson. Social positions and simulation relations. Social Network Analysis and Mining , 2(1):39–52, 2012. doi:10.1007/s13278-011-0032-x

work page doi:10.1007/s13278-011-0032-x 2012
[10]

Partitioning a graph in O(|A|log2|V|)

Alain Cardon and Maxime Crochemore. Partitioning a graph in O(|A|log2|V|). Theoretical Computer Science, 19(1):85–98, 1982. doi:10.1016/0304-3975(82)90016-0

work page doi:10.1016/0304-3975(82)90016-0 1982
[11]

Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

Ching-Lueh Chang, Yuh-Dauh Lyuu, and Yen-Wu Ti. The complexity of Tarski’s fixed point theorem. Theoretical Computer Science, 401(1-3):228–235, 2008. doi:10.1016/j.tcs. 2008.05.005

work page doi:10.1016/j.tcs 2008
[12]

Improved upper bounds for finding Tarski fixed points

Xi Chen and Yuhao Li. Improved upper bounds for finding Tarski fixed points. InProceedings of the 23rd ACM Conference on Economics and Computation , pages 1108–1118, Boulder CO USA, 2022. ACM. doi:10.1145/3490486.3538297

work page doi:10.1145/3490486.3538297 2022
[13]

Reducing Tarski to unique Tarski (in the black-box model)

Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to unique Tarski (in the black-box model). In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 21:1–21:23, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. doi:10...

work page doi:10.4230/lipics.ccc.2023.21 2023
[14]

Computations and complexities of Tarski’s fixed points and supermodular games

Chuangyin Dang, Qi Qi, and Yinyu Ye. Computations and complexities of Tarski’s fixed points and supermodular games. arXiv, 2005.09836 [cs, econ], 2020. arXiv:2005.09836, doi:10.48550/ARXIV.2005.09836

work page doi:10.48550/arxiv.2005.09836 2005
[15]

The complexity of determining the uniqueness of Tarski’s fixed point under the lexicographic ordering

Chuangyin Dang and Yinyu Ye. The complexity of determining the uniqueness of Tarski’s fixed point under the lexicographic ordering. In Amin Saberi, editor, Internet and Network Economics, volume 6484 of Lecture Notes in Computer Science , pages 455–461. Springer, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-17572-5_38 . 16

work page doi:10.1007/978-3-642-17572-5_38 2010
[16]

Davey & Hilary A

Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order . Cambridge University Press, Cambridge, 2 edition, 2002. doi:10.1017/CBO9780511809088

work page doi:10.1017/cbo9780511809088 2002
[17]

Cam- bridge University Press, Cambridge, 1 edition, 2005

Patrick Doreian, Vladimir Batagelj, and Anuˇ ska Ferligoj.Generalized Blockmodeling. Cam- bridge University Press, Cambridge, 1 edition, 2005. doi:10.1017/CBO9780511584176

work page doi:10.1017/cbo9780511584176 2005
[18]

Finding all equilibria in games of strategic complements

Federico Echenique. Finding all equilibria in games of strategic complements. Journal of Economic Theory, 135(1):514–532, 2007. doi:10.1016/j.jet.2006.06.001

work page doi:10.1016/j.jet.2006.06.001 2007
[19]

In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s theorem, supermodular games, and the complexity of equilibria. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:19, Dagstuhl, G...

work page doi:10.4230/lipics 2020
[20]

Everett and Stephen P

Martin G. Everett and Stephen P. Borgatti. Role colouring a graph. Mathematical Social Sciences, 21(2):183–188, 1991. doi:10.1016/0165-4896(91)90080-B

work page doi:10.1016/0165-4896(91)90080-b 1991
[21]

A faster algorithm for finding Tarski fixed points

John Fearnley, D¨ om¨ ot¨ or P´ alv¨ olgyi, and Rahul Savani. A faster algorithm for finding Tarski fixed points. ACM Transactions on Algorithms, page 3524044, 2022. doi:10.1145/3524044

work page doi:10.1145/3524044 2022
[22]

A complete complexity classification of the role assignment problem

Jiˇ r´ ı Fiala and Dani¨ el Paulusma. A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1):67–81, 2005. doi:10.1016/j.tcs.2005.09. 029

work page doi:10.1016/j.tcs.2005.09 2005
[23]

Birkh¨ auser, Basel Berlin, 2

George Gr¨ atzer.General Lattice Theory. Birkh¨ auser, Basel Berlin, 2. ed edition, 2003

work page 2003
[24]

Henzinger, Thomas A

Monika R. Henzinger, Thomas A. Henzinger, and Peter W. Kopke. Computing simulations on finite and infinite graphs. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 453–462, Milwaukee, WI, USA, 1995. IEEE Computer Society Press. doi: 10.1109/SFCS.1995.492576

work page doi:10.1109/sfcs.1995.492576 1995
[25]

Johnson, Mihalis Yannakakis, and Christos H

David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988. doi: 10.1016/0020-0190(88)90065-8

work page doi:10.1016/0020-0190(88)90065-8 1988
[26]

An algebraic definition of simulation between programs

Robin Milner. An algebraic definition of simulation between programs. In Proceedings of the Second International Joint Conference on Artificial Intelligence (IJCAI 1971) , pages 481–489, London, 1971

work page 1971
[27]

Communication and Concurrency

Robin Milner. Communication and Concurrency. Prentice Hall, Englewood Cliffs, NJ, 1989

work page 1989
[28]

netroles library for role equivalence analysis in networks version 0.1

Julian M¨ uller. netroles library for role equivalence analysis in networks version 0.1. Zenodo,

work page
[29]

doi:10.5281/ZENODO.8199503

work page doi:10.5281/zenodo.8199503
[30]

The evolution of roles

Julian M¨ uller and Ulrik Brandes. The evolution of roles. Social Networks, 68:195–208, 2022. doi:10.1016/j.socnet.2021.02.001

work page doi:10.1016/j.socnet.2021.02.001 2022
[31]

Robert Paige and Robert E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973–989, 1987. doi:10.1137/0216062

work page doi:10.1137/0216062 1987
[32]

Concurrency and automata on infinite sequences

David Park. Concurrency and automata on infinite sequences. In Peter Deussen, editor, Proceedings of the 5th GI-Conference on Theoretical Computer Science , volume 104 of Lecture Notes in Computer Science, pages 167–183, Berlin/Heidelberg, 1981. Springer-Verlag. doi:10.1007/BFb0017309

work page doi:10.1007/bfb0017309 1981
[33]

Rennie and A.J

B.C. Rennie and A.J. Dobson. On Stirling numbers of the second kind. Journal of Combinatorial Theory, 7(2):116–121, 1969. doi:10.1016/S0021-9800(69)80045-1. 17

work page doi:10.1016/s0021-9800(69)80045-1 1969
[34]

Roberts and Li Sheng

Fred S. Roberts and Li Sheng. How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67–73, 2001. doi:10.1002/1097-0037(200103)37:2<67:: AID-NET1>3.0.CO;2-9

work page doi:10.1002/1097-0037(200103)37:2 2001
[35]

Lee D. Sailer. Structural equivalence: Meaning and definition, computation and application. Social Networks, 1(1):73–90, 1978. doi:10.1016/0378-8733(78)90014-X

work page doi:10.1016/0378-8733(78)90014-x 1978
[36]

ACM Trans

Davide Sangiorgi. On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems, 31(4):1–41, 2009. doi:10.1145/1516507.1516510

work page doi:10.1145/1516507.1516510 2009
[37]

Ein Satz ¨ uber Untermengen einer endlichen Menge

Emanuel Sperner. Ein Satz ¨ uber Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27(1):544–548, 1928. doi:10.1007/BF01171114

work page doi:10.1007/bf01171114 1928
[38]

A lattice-theoretical ﬁxpoint theorem and its applications,

Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285–309, June 1955. doi:10.2140/pjm.1955.5.285

work page doi:10.2140/pjm.1955.5.285 1955
[39]

White and Karl P

Douglas R. White and Karl P. Reitz. Graph and semigroup homomorphisms on networks of relations. Social Networks, 5(2):193–234, 1983. doi:10.1016/0378-8733(83)90025-4. 18

work page doi:10.1016/0378-8733(83)90025-4 1983

[1] [2]

Bard Bloom, Sorin Istrail, and Albert R. Meyer. Bisimulation can’t be traced. Journal of the ACM, 42(1):232–268, January 1995. doi:10.1145/200836.200876

work page doi:10.1145/200836.200876 1995

[2] [3]

Transformational design and implementation of a new efficient solution to the ready simulation problem

Bard Bloom and Robert Paige. Transformational design and implementation of a new efficient solution to the ready simulation problem. Science of Computer Programming , 24(3):189–220, 1995. doi:10.1016/0167-6423(95)00003-B

work page doi:10.1016/0167-6423(95)00003-b 1995

[3] [4]

Borgatti, John P

Stephen P. Borgatti, John P. Boyd, and Martin G. Everett. Iterated roles: Mathematics and application. Social Networks, 11(2):159–172, 1989. doi:10.1016/0378-8733(89)90010-5

work page doi:10.1016/0378-8733(89)90010-5 1989

[4] [5]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. The class of all regular equivalences: Al- gebraic structure and computation. Social Networks, 11(1):65–88, 1989. doi:10.1016/ 0378-8733(89)90018-X

work page 1989

[5] [6]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. Graph colorings and power in experimental exchange networks. Social Networks, 14(3-4):287–308, 1992. doi:10.1016/0378-8733(92) 90006-S

work page doi:10.1016/0378-8733(92 1992

[6] [7]

Borgatti and Martin G

Stephen P. Borgatti and Martin G. Everett. Ecological and perfect colorings. Social Networks, 16(1):43–55, 1994. doi:10.1016/0378-8733(94)90010-8

work page doi:10.1016/0378-8733(94)90010-8 1994

[7] [8]

Boyd and Martin G

John P. Boyd and Martin G. Everett. Relations, residuals, regular interiors, and relative regular equivalence. Social Networks, 21(2):147–165, 1999. doi:10.1016/S0378-8733(99) 00006-4

work page doi:10.1016/s0378-8733(99 1999

[8] [9]

Social positions and simulation relations

Joel Brynielsson, Lisa Kaati, and Pontus Svenson. Social positions and simulation relations. Social Network Analysis and Mining , 2(1):39–52, 2012. doi:10.1007/s13278-011-0032-x

work page doi:10.1007/s13278-011-0032-x 2012

[9] [10]

Partitioning a graph in O(|A|log2|V|)

Alain Cardon and Maxime Crochemore. Partitioning a graph in O(|A|log2|V|). Theoretical Computer Science, 19(1):85–98, 1982. doi:10.1016/0304-3975(82)90016-0

work page doi:10.1016/0304-3975(82)90016-0 1982

[10] [11]

Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

Ching-Lueh Chang, Yuh-Dauh Lyuu, and Yen-Wu Ti. The complexity of Tarski’s fixed point theorem. Theoretical Computer Science, 401(1-3):228–235, 2008. doi:10.1016/j.tcs. 2008.05.005

work page doi:10.1016/j.tcs 2008

[11] [12]

Improved upper bounds for finding Tarski fixed points

Xi Chen and Yuhao Li. Improved upper bounds for finding Tarski fixed points. InProceedings of the 23rd ACM Conference on Economics and Computation , pages 1108–1118, Boulder CO USA, 2022. ACM. doi:10.1145/3490486.3538297

work page doi:10.1145/3490486.3538297 2022

[12] [13]

Reducing Tarski to unique Tarski (in the black-box model)

Xi Chen, Yuhao Li, and Mihalis Yannakakis. Reducing Tarski to unique Tarski (in the black-box model). In Amnon Ta-Shma, editor, 38th Computational Complexity Conference (CCC 2023), volume 264 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 21:1–21:23, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. doi:10...

work page doi:10.4230/lipics.ccc.2023.21 2023

[13] [14]

Computations and complexities of Tarski’s fixed points and supermodular games

Chuangyin Dang, Qi Qi, and Yinyu Ye. Computations and complexities of Tarski’s fixed points and supermodular games. arXiv, 2005.09836 [cs, econ], 2020. arXiv:2005.09836, doi:10.48550/ARXIV.2005.09836

work page doi:10.48550/arxiv.2005.09836 2005

[14] [15]

The complexity of determining the uniqueness of Tarski’s fixed point under the lexicographic ordering

Chuangyin Dang and Yinyu Ye. The complexity of determining the uniqueness of Tarski’s fixed point under the lexicographic ordering. In Amin Saberi, editor, Internet and Network Economics, volume 6484 of Lecture Notes in Computer Science , pages 455–461. Springer, Berlin, Heidelberg, 2010. doi:10.1007/978-3-642-17572-5_38 . 16

work page doi:10.1007/978-3-642-17572-5_38 2010

[15] [16]

Davey & Hilary A

Brian A. Davey and Hilary A. Priestley. Introduction to Lattices and Order . Cambridge University Press, Cambridge, 2 edition, 2002. doi:10.1017/CBO9780511809088

work page doi:10.1017/cbo9780511809088 2002

[16] [17]

Cam- bridge University Press, Cambridge, 1 edition, 2005

Patrick Doreian, Vladimir Batagelj, and Anuˇ ska Ferligoj.Generalized Blockmodeling. Cam- bridge University Press, Cambridge, 1 edition, 2005. doi:10.1017/CBO9780511584176

work page doi:10.1017/cbo9780511584176 2005

[17] [18]

Finding all equilibria in games of strategic complements

Federico Echenique. Finding all equilibria in games of strategic complements. Journal of Economic Theory, 135(1):514–532, 2007. doi:10.1016/j.jet.2006.06.001

work page doi:10.1016/j.jet.2006.06.001 2007

[18] [19]

In 32nd European Conference on Object-Oriented Programming (ECOOP 2018)

Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s theorem, supermodular games, and the complexity of equilibria. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) , volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:19, Dagstuhl, G...

work page doi:10.4230/lipics 2020

[19] [20]

Everett and Stephen P

Martin G. Everett and Stephen P. Borgatti. Role colouring a graph. Mathematical Social Sciences, 21(2):183–188, 1991. doi:10.1016/0165-4896(91)90080-B

work page doi:10.1016/0165-4896(91)90080-b 1991

[20] [21]

A faster algorithm for finding Tarski fixed points

John Fearnley, D¨ om¨ ot¨ or P´ alv¨ olgyi, and Rahul Savani. A faster algorithm for finding Tarski fixed points. ACM Transactions on Algorithms, page 3524044, 2022. doi:10.1145/3524044

work page doi:10.1145/3524044 2022

[21] [22]

A complete complexity classification of the role assignment problem

Jiˇ r´ ı Fiala and Dani¨ el Paulusma. A complete complexity classification of the role assignment problem. Theoretical Computer Science, 349(1):67–81, 2005. doi:10.1016/j.tcs.2005.09. 029

work page doi:10.1016/j.tcs.2005.09 2005

[22] [23]

Birkh¨ auser, Basel Berlin, 2

George Gr¨ atzer.General Lattice Theory. Birkh¨ auser, Basel Berlin, 2. ed edition, 2003

work page 2003

[23] [24]

Henzinger, Thomas A

Monika R. Henzinger, Thomas A. Henzinger, and Peter W. Kopke. Computing simulations on finite and infinite graphs. In Proceedings of IEEE 36th Annual Foundations of Computer Science, pages 453–462, Milwaukee, WI, USA, 1995. IEEE Computer Society Press. doi: 10.1109/SFCS.1995.492576

work page doi:10.1109/sfcs.1995.492576 1995

[24] [25]

Johnson, Mihalis Yannakakis, and Christos H

David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. On generating all maximal independent sets. Information Processing Letters, 27(3):119–123, 1988. doi: 10.1016/0020-0190(88)90065-8

work page doi:10.1016/0020-0190(88)90065-8 1988

[25] [26]

An algebraic definition of simulation between programs

Robin Milner. An algebraic definition of simulation between programs. In Proceedings of the Second International Joint Conference on Artificial Intelligence (IJCAI 1971) , pages 481–489, London, 1971

work page 1971

[26] [27]

Communication and Concurrency

Robin Milner. Communication and Concurrency. Prentice Hall, Englewood Cliffs, NJ, 1989

work page 1989

[27] [28]

netroles library for role equivalence analysis in networks version 0.1

Julian M¨ uller. netroles library for role equivalence analysis in networks version 0.1. Zenodo,

work page

[28] [29]

doi:10.5281/ZENODO.8199503

work page doi:10.5281/zenodo.8199503

[29] [30]

The evolution of roles

Julian M¨ uller and Ulrik Brandes. The evolution of roles. Social Networks, 68:195–208, 2022. doi:10.1016/j.socnet.2021.02.001

work page doi:10.1016/j.socnet.2021.02.001 2022

[30] [31]

Robert Paige and Robert E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973–989, 1987. doi:10.1137/0216062

work page doi:10.1137/0216062 1987

[31] [32]

Concurrency and automata on infinite sequences

David Park. Concurrency and automata on infinite sequences. In Peter Deussen, editor, Proceedings of the 5th GI-Conference on Theoretical Computer Science , volume 104 of Lecture Notes in Computer Science, pages 167–183, Berlin/Heidelberg, 1981. Springer-Verlag. doi:10.1007/BFb0017309

work page doi:10.1007/bfb0017309 1981

[32] [33]

Rennie and A.J

B.C. Rennie and A.J. Dobson. On Stirling numbers of the second kind. Journal of Combinatorial Theory, 7(2):116–121, 1969. doi:10.1016/S0021-9800(69)80045-1. 17

work page doi:10.1016/s0021-9800(69)80045-1 1969

[33] [34]

Roberts and Li Sheng

Fred S. Roberts and Li Sheng. How hard is it to determine if a graph has a 2-role assignment? Networks, 37(2):67–73, 2001. doi:10.1002/1097-0037(200103)37:2<67:: AID-NET1>3.0.CO;2-9

work page doi:10.1002/1097-0037(200103)37:2 2001

[34] [35]

Lee D. Sailer. Structural equivalence: Meaning and definition, computation and application. Social Networks, 1(1):73–90, 1978. doi:10.1016/0378-8733(78)90014-X

work page doi:10.1016/0378-8733(78)90014-x 1978

[35] [36]

ACM Trans

Davide Sangiorgi. On the origins of bisimulation and coinduction. ACM Transactions on Programming Languages and Systems, 31(4):1–41, 2009. doi:10.1145/1516507.1516510

work page doi:10.1145/1516507.1516510 2009

[36] [37]

Ein Satz ¨ uber Untermengen einer endlichen Menge

Emanuel Sperner. Ein Satz ¨ uber Untermengen einer endlichen Menge. Mathematische Zeitschrift, 27(1):544–548, 1928. doi:10.1007/BF01171114

work page doi:10.1007/bf01171114 1928

[37] [38]

A lattice-theoretical ﬁxpoint theorem and its applications,

Alfred Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285–309, June 1955. doi:10.2140/pjm.1955.5.285

work page doi:10.2140/pjm.1955.5.285 1955

[38] [39]

White and Karl P

Douglas R. White and Karl P. Reitz. Graph and semigroup homomorphisms on networks of relations. Social Networks, 5(2):193–234, 1983. doi:10.1016/0378-8733(83)90025-4. 18

work page doi:10.1016/0378-8733(83)90025-4 1983