# Extensions of the Schur majorisation inequalities

Rajendra Bhatia  Ashoka University, Sonepat, Haryana, 131029, India  Rajesh
Sharma  Department of Mathematics and Statistics, H.P. University, Shimla-5,
India

###### Abstract

Let $\lambda_{j}$ and $a_{jj}$, $1\leq j\leq n,$ be the eigenvalues and the
diagonal entries of a Hermitian matrix $A$, both enumerated in the increasing
order. We prove some inequalities that are stronger than the Schur
majorisation inequalities $\sum_{j=1}^{r}\lambda_{j}\leq\sum_{j=1}^{r}a_{jj},$
$1\leq r\leq n.$

###### keywords:

Hermitian matrix, Spectrum, Majorisation, Positive linear functionals.

###### MSC:

[2020] 15A18, 15A42, 15B57.

††journal: Journal of LaTeX Templates

##  1 Introduction

Let $A$ be an $n\times n$ complex Hermitian matrix. Let the eigenvalues and
the diagonal entries of $A$ both be enumerated in increasing order as

$\lambda_{1}(A)\leq\lambda_{2}(A)\leq\dots\leq\lambda_{n}(A),$ (1.1)

and

$a_{11}\leq a_{22}\leq\dots\leq a_{nn},$ (1.2)

respectively. We then have

$\lambda_{1}(A)\leq a_{11}\quad\text{and}\quad\lambda_{n}(A)\geq a_{nn}.$
(1.3)

These inequalities are included in the Schur majorisation inequalities that
say: for every $1\leq r\leq n$

$\sum_{j=1}^{r}\lambda_{j}(A)\leq\sum_{j=1}^{r}a_{jj},$ (1.4)

with equality in the case $r=n.$ These inequalities are of fundamental
importance in matrix analysis and have been the subject of intensive work.
See, e.g. Bhatia [1], Horn and Johnson [4] and Marshal and Olkin [5].
In this note we obtain some inequalities that are stronger than (1.3) and
(1.4). These give estimates of eigenvalues in terms of quantities easily
computable from the entries of $A.$

Given the $n\times n$ Hermitian matrix $A=\left[a_{ij}\right],$ let

$r_{i}=\sum_{j\neq i}\left|\ a_{ij}\right|,\quad 1\leq i\leq n$ (1.5)

and

$q_{i}=\sum_{j\neq i}\left|\ a_{ij}\right|^{2},\quad 1\leq i\leq n.$ (1.6)

A permutation similarity does not change either the eigenvalues or the
diagonal entries of $A.$ Nor does it change the quantities $r_{i}$ and
$q_{i}.$ We assume that such a permutation similarity has been performed and
the ordering (1.2) for diagonal entries has been achieved. To rule out trivial
cases, we assume that $A$ is not a diagonal matrix.
Our first theorem is a strengthening of the inequalities (1.3).

###### Theorem 1

For every $n\times n$ Hermitian matrix $A$, we have

$\lambda_{1}(A)\leq a_{11}-\frac{q_{1}}{\max_{i}(a_{ii}+r_{i})-a_{11}},$ (1.7)

$\lambda_{n}(A)\geq a_{nn}+\frac{q_{n}}{a_{nn}-\min_{i}(a_{ii}-r_{i})}.$ (1.8)

The next two theorems give inequalities stronger than (1.4).

###### Theorem 2

Let $A$ be an $n\times n$ Hermitian matrix. Then for $1\leq r\leq n-1$ and
$r<t\leq n$, we have

$\sum_{i=1}^{r}\lambda_{i}(A)\leq\sum_{i=1}^{r}a_{ii}-\frac{\sum_{s=1}^{r}\left|\
a_{ts}\right|^{2}}{a_{tt}-\min_{i=1,...,r,t}\left(a_{ii}-\sum_{\begin{subarray}{c}s=1\\\
s\neq i\end{subarray}}^{r+1}\left|\ a_{is}\right|\right)}.$ (1.9)

###### Theorem 3

Let $A$ be an $n\times n$ Hermitian matrix. Then for $1\leq r\leq n-1$, $1\leq
k\leq r$, and $r<t\leq n$, we have

$\sum_{i=1}^{r}\lambda_{i}(A)\leq\sum_{i=1}^{r}a_{ii}-\frac{\sqrt{(a_{tt}-a_{kk})^{2}+4|a_{tk}|^{2}}-(a_{tt}-a_{kk})}{2}.$
(1.10)

##  2 Proofs

Our proofs rely upon two basic theorems of matrix analysis. Let
$\mathbb{M}(n)$ be the algebra of all $n\times n$ complex matrices and let
$\Phi:\mathbb{M}(n)\rightarrow\mathbb{M}(k)$ be a positive unital linear map,
[3]. Then the Bhatia-Davis inequality [2] says that for every Hermitian matrix
$A$ whose spectrum is contained in the interval $\left[m,M\right],$ we have

$\Phi\left(A^{2}\right)-\Phi\left(A\right)^{2}\leq\left(MI-\Phi\left(A\right)\right)\left(\Phi\left(A\right)-mI\right)\leq\left(\frac{M-m}{2}\right)^{2}I.$
(2.1)

Cauchy’s interlacing principle says that if $A_{r}$ is an $r\times r$
principal submatrix of $A,$ then

$\lambda_{j}(A)\leq\lambda_{j}(A_{r}),\quad 1\leq j\leq r.$ (2.2)

See Chapter III of [1] for this and other facts used here.

###  2.1 Proof of Theorem 1

Let $\varphi:\mathbb{M}(n)\rightarrow\mathbb{C}$ be a positive unital linear
functional and let the eigenvalues of Hermitian element $A\in\mathbb{M}(n)$ be
arranged as in (1.1). From the first inequality (2.1), we have

$\varphi\left(A^{2}\right)-\varphi\left(A\right)^{2}\leq\left(\lambda_{n}(A)-\varphi\left(A\right)\right)\left(\varphi\left(A\right)-\lambda_{1}(A)\right).$
(2.3)

Suppose $\lambda_{n}(A)\neq\varphi(A)$. Then, from (2.3), we have

$\lambda_{1}(A)\leq\varphi(A)-\frac{\varphi\left(A^{2}\right)-\varphi\left(A\right)^{2}}{\lambda_{n}(A)-\varphi\left(A\right)}.$
(2.4)

Further, by the Gersgorin disk theorem, we have

$\lambda_{n}(A)\leq\text{max}_{i}(a_{ii}+r_{i}).$ (2.5)

Combining (2.4) and (2.5), we get

$\lambda_{1}(A)\leq\varphi(A)-\frac{\varphi\left(A^{2}\right)-\varphi\left(A\right)^{2}}{\text{max}_{i}(a_{ii}+r_{i})-\varphi\left(A\right)}.$
(2.6)

Choose $\varphi(A)=a_{11}$. Then, $\varphi$ is a positive unital linear
functional and $\varphi\left(A^{2}\right)-\varphi\left(A\right)^{2}=q_{1}$.
So, (2.6) yields (1.7).
Suppose $\lambda_{n}(A)=\varphi(A)=a_{11}.$ Then, from (1.2) and (1.3), we
have $a_{11}=a_{22}=\dots=a_{nn}$ and from (2.3),
$\varphi\left(A^{2}\right)-\varphi\left(A\right)^{2}=0.$ Therefore, $q_{i}=0$
for all $i=1,2,...,n$. But then $A$ is a scalar matrix.
The inequality (1.8) follows on using similar arguments. The derivation
requires lower bound of $\lambda_{n}(A)$ from (2.3) which is analogous to
(2.4), $\lambda_{1}(A)\geq\min_{i}\left(a_{ii}-r_{i}\right)$ and
$\varphi\left(A\right)=a_{nn}$. ∎

###  2.2 Proof of Theorem 2

The trace of $A$ is the sum of the eigenvalues of $A$. Therefore,

$\lambda_{n}(A)=\text{tr}A-\sum_{i=1}^{n-1}\lambda_{i}(A).$ (2.7)

Combining (1.8) and (2.7), we find that

$\sum_{i=1}^{n-1}\lambda_{i}(A)\leq\sum_{i=1}^{n-1}a_{ii}-\frac{q_{n}}{a_{nn}-\min_{i}(a_{ii}-r)}.$
(2.8)

Apply (2.8) to the principal submatrix $P$ of $A$ containing diagonal entries
$a_{11},a_{22},...,a_{rr},a_{tt},$ we get that

$\sum_{i=1}^{r}\lambda_{i}(P)\leq\sum_{i=1}^{r}a_{ii}-\frac{\sum_{s=1}^{r}\left|\
a_{ts}\right|^{2}}{a_{tt}-\min_{i=1,...,r,t}\left(a_{ii}-\sum_{\begin{subarray}{c}s=1\\\
s\neq i\end{subarray}}^{r+1}\left|\ a_{is}\right|\right)}.$ (2.9)

By the interlacing inequalities (2.2),
$\sum_{i=1}^{r}\lambda_{i}(A)\leq\sum_{i=1}^{r}\lambda_{i}(P)$. So, (2.9)
gives (1.9). ∎

###  2.3 Proof of Theorem 3

By the Cauchy interlacing principle (2.2), the largest eigenvalue of $A$ is
greater than or equal to the largest eigenvalue of any $2\times 2$ principal
submatrix of $A$. Further, the eigenvalues of
$\left[\begin{array}[]{cc}a_{rr}&a_{rs}\\\
\overline{a_{rs}}&a_{ss}\end{array}\right]$are
$\frac{1}{2}\left(a_{rr}+a_{ss}\pm\sqrt{(a_{rr}-a_{ss})^{2}+4|a_{rs}|^{2}}\right)$.
On using these two facts, we see that

$\lambda_{n}(A)\geq
a_{nn}+\frac{\sqrt{(a_{nn}-a_{kk})^{2}+4|a_{kn}|^{2}}-(a_{nn}-a_{kk})}{2}$
(2.10)

for all $k=1,2,...,n-1.$ Combining (2.7) and (2.10), we find that

$\sum_{i=1}^{n-1}\lambda_{i}(A)\leq\sum_{i=1}^{n-1}a_{ii}-\frac{\sqrt{(a_{nn}-a_{kk})^{2}+4|a_{kn}|^{2}}-(a_{nn}-a_{kk})}{2}.$
(2.11)

Apply (2.11) to the principal submatrix $Q$ of $A$ containing
$a_{11},a_{22},...,a_{rr},a_{tt}$, we find that for $k=1,2,...,r,$ we have

$\sum_{i=1}^{r}\lambda_{i}(Q)\leq\sum_{i=1}^{r}a_{ii}-\frac{\sqrt{(a_{tt}-a_{kk})^{2}+4|a_{tk}|^{2}}-(a_{tt}-a_{kk})}{2}.$
(2.12)

The inequality (2.12) yields (1.10), on using the interlacing inequalities
(2.2). ∎

We show by means of an example that (1.9) and (1.10) are independent.

###### Example 1

Let

$A=\left[\begin{array}[]{ccc}2&1&1\\\ 1&2&1\\\ 1&1&3\end{array}\right],\quad
B=\left[\begin{array}[]{ccc}1&2&3\\\ 2&1&4\\\ 3&4&1\end{array}\right].$

Then (1.9) gives the estimate $\lambda_{1}(A)+\lambda_{2}(A)<\frac{10}{3}$,
while (1.10) gives the weaker estimate $\frac{9-\sqrt{5}}{2}$ for the same
quantity. On the other hand from (1.9) we get that
$\lambda_{1}(B)+\lambda_{2}(B)<-\frac{11}{7}$, while from (1.10) we see that
the same quantity is not bigger than $-2$.

## References

  * [1] Bhatia R., _Matrix Analysis_ , Springer, New York, (1997).
  * [2] Bhatia R., Davis C., _A better bound on the variance_ , Amer. Math. Monthly, 107, (2000), 353-357.
  * [3] Bhatia R., _Positive Definite Matrices_ , Princeton University Press, (2007).
  * [4] Horn R.A., Johnson C.R., _Matrix Analysis_ , Cambridge University Press, (2013).
  * [5] Marshal A.W., Olkin I., _Inequalities: Theory of Majorisation and its applications_ , Academic Press, (1979).


# Retrospectively Diagnosing Einstein with Asperger’s Syndrome and the Dismal
Failure of Debunking Myths

Galina Weinstein  Reichman University, The Efi Arazi School of Computer
Science, Herzliya; University of Haifa, The Department of Philosophy, Haifa,
Israel.

###### Abstract

In 2003, Simon Baron-Cohen, a world expert on autism, diagnosed Einstein
posthumously with Asperger’s syndrome. I think we cannot diagnose a dead
person. Historians of science have fiercely objected to this trend of
diagnosing deceased scientists by reconstructing from scant evidence, calling
these diagnoses myths. Despite the historians’ efforts at demolishing myths,
Einstein has been constantly diagnosed with Asperger’s syndrome. I will stick
my neck out and suggest in this paper that although historians’ critique of
Baron-Cohen and others includes debunking myths, it piggybacks on another myth
that uses the following metaphors: a dull and socially adept Einstein who
worked at Zurich, Prague, Berlin, and Princeton, an industrious scientist who
earned his living through his work as a professor at the university; he had a
special gift of friendship and collegiality, and he was deeply embedded in the
academic community. These explanations do not make sense from the perspective
of Einstein sitting in his office at Princeton, let alone Einstein sitting in
the patent office. This perhaps explains the tendency of people to find
counterclaims and myths more persuasive than historians’ explanations which
seem deeply problematic.

##  1 Introduction

With some apprehension, I lectured about retrospectively diagnosing Einstein
with autism (Asperger’s syndrome) at the conference ”Actually Autism” at Ben-
Gurion University. I was reluctant to meddle in Einstein’s private life. I
prefer to occupy myself with Einstein’s physics. I decided to get involved in
this topic and give this lecture because in trying to debunk myths, people
simply spread stigmas and prejudices about Asperger’s syndrome and twist
Einstein’s biography. This paper presents an adapted version of my lecture.

Why does everybody ask if Albert Einstein had Asperger’s syndrome? Because –
as I show in section 2 – in 2003, Simon Baron-Cohen made a posthumous
diagnosis of Einstein, suggesting he showed many signs of Asperger’s
syndrome.111Here is a list of signs of twice-exceptionality and Asperger’s
syndrome in adults (including the following but not limited to these): 1\.
Lack of cognitive empathy (finding it hard to understand what others are
thinking and feeling) and high empathic concern (desire to reduce other
people’s suffering and help them at your own expense). 2\. Have the same daily
routine and get anxious if it changes. 3\. Have meltdowns (tantrums),
difficulty managing emotions leading to outbursts, and may seem blunt and
rude. 4\. Are autodidacts (can teach themselves just about anything). 5\. May
have weak short-term memory and very strong long-term memory. May have a
visual memory. 6\. Can be atheistic or leave one religion and enter another.
7\. Have a spiky profile of strengths and weaknesses. 8\. May have dropped out
of high school and returned later; may have unfinished or partial degrees. May
have dropped out of classes and not attended classes. 9\. May have difficulty
accepting criticism, stubbornness, and fixation on topics. 10\. Having
problems expressing themselves clearly, and talking and laughing very loudly,
though there is little to laugh about. 11\. Attention to details. 12\. Tends
to burn bridges with people and may rebel against authority. 13\. Considered a
”loner” and needs more time than others to be alone; has difficulty
socializing for extended periods; wants to spend time socializing but is
overstimulated by too many people. Does not just focuses around the clock on a
special interest that may involve the person’s career. Tends to be easily
overwhelmed by noises and in social situations and then withdraws to a quiet
spot; needs more time alone than others. 14\. Has a high sense of justice and
fairness and is too honest. 15\. On the one hand, they can be witty and
sarcastic and tend to be more childish; on the other, they can take things
very literally and may not understand sarcasm, irony, or humor from other
people. May use humor to overcome social obstacles by playing tricks on
others. 16\. Have a remarkable power of concentration and can focus for long
periods of time on the special interest without eating or drinking. 17\.
Unusual tolerance for unconventional and unorthodox thinking and people. 18\.
May dress differently than their peers; often appear eccentric; dress more for
comfort than appearance. 19\. May invent limericks and send them to people
they care about. 20\. May feel things profoundly and experience intense
emotions. From: Autism Awareness Centre Inc.  Baron-Cohen has argued that in
several biographies of Einstein, it was written that Einstein was a loner and
could not speak until he was three. Baron-Cohen did not base his retrospective
diagnosis on historical medical records written by physicians. He instead
diagnosed Einstein based on fragments of evidence mainly found in biographies.

As I discuss in section 3, several caveats exist in diagnosing a dead person
retrospectively. The danger with historical retro-diagnosis is that the
details of Einstein’s thinking process are not always precise, and we cannot
extract a few details from a biography. Indeed, as I show in this paper,
medical historians object to this practice saying that experts usually read a
biography, extract some passages dealing with medicine, and come up with a
diagnosis. What is even more insidious is that retro-diagnosis is made by
people who are amateur historians rather than historiographical-trained
scholars. They, therefore, even often draw on dubious sources to make
historical diagnoses. Further, people retrospectively diagnosing historical
figures are susceptible to biases. A controversy has erupted over the retro-
diagnosis of Einstein. Historians of science have fiercely objected to this
trend of diagnosing deceased scientists retrospectively by reconstructing from
scant evidence. Despite the historians’ warning, Einstein has been constantly
diagnosed with Asperger’s syndrome.

In the end, in section 4, I show that there is a twist to the story. It turns
out that historians are susceptible to biases, precisely like any other
scholar.

##  2 Baron-Cohen diagnoses Einstein

It all started when Simon Baron-Cohen, a professor of developmental
psychopathology and a world expert on autism at Cambridge University,
suggested that Einstein might have shown signs of Asperger’s syndrome [3].
Baron-Cohen supports his thesis by 1) quoting an account by Einstein’s son
Hans Albert written by Peter Michelmore in his biography of Einstein,
_Einstein, Profile of the Man_ ,222Michelmore begins his book by saying: ”In
February, 1962, I spent two days with Hans Albert Einstein in his home
overlooking San Francisco Bay. Hans Albert, fifty-seven, the older son of
Albert Einstein […]. He had never discussed his father before with any writer,
at least not in depth. But he answered all my questions and waited while I
wrote down the answers.” and 2) cherry-picking Einstein’s idiosyncratic habits
from Roger Highfield and Paul Carter’s book, _The Private Lives of Albert
Einstein_.333The authors base their stories on family members’ reports and
memories of people who knew Einstein. Baron-Cohen writes [3]:

> Einstein was described as ”lonely and dreamy” as a child, with difficulty in
> making friends. He was said to prefer ”solitary and taxing” games, such as
> complex constructional play with blocks or making houses of cards up to
> fourteen stories high. He would ”softly repeat every sentence he uttered—a
> habit he continued until the age of seven.” He was still not considered
> fluent in speech at the age of nine. He was also a loner: ”I’m not much with
> people,” he would say. ”I do not socialize because social encounters would
> distract me from my work and I really only live for that, and it would
> shorten even further my very limited lifespan.”

This is almost verbatim what Highfield and Carter write in their book. 444The
first part of Baron-Cohen’s quotation is based on the following passage from
Highfield and Carter [20]:  By his description [to Bela Kornitzer], Einstein
was a lonely and dreamy child who did not easily find companions. He would
avoid the rough-and-tumble games when the children of relatives came to play
in the Einsteins’ garden, […]. Besides assembling complicated constructions
with his building blocks, he made houses of cards up to fourteen stories high.
[…] After starting to talk comparatively late, he would softly repeat every
sentence he uttered - a habit that continued until he was seven. Even when he
was nine he lacked fluency of speech. The problem seems to have been as much a
reluctance to communicate as any inability to do so. The second part of
Highfield and Carter’s paragraph (”Besides assembling […]”) is based on Maja
Winteler-Einstein’s (Einstein’s sister) biography of her brother [39]. The
second part of Baron-Cohen’s quotation is based on the following passage from
Highfield and Carter [20]:  ’I’m not much with people, and I’m not a family
man.’ he told Salaman. ’I want my peace. I want to know how God created this
world.’ Esther Salaman was a young Jewish woman who interviewed Einstein in
Berlin but published the interview thirty years after Einstein died in 1955.
And the full quote is [35]:  ”I’m not much with people, and I’m not a family
man. I want my peace. I want to know how God created this world. I am not
interested in this or that phenomenon, in the spectrum of this or that
element. I want to know His thoughts; the rest are details.” The phrase ”God
created the world,” so often repeated by Einstein, represents his religious
feeling that laws of nature could be formulated in the simplest form. The
quotation ”I do not socialize because social encounters would distract me from
my work” is taken from the following source. Einstein’s physician and friend
Janos Plesch writes [33]:  On suitable occasions, one could also get from him
[Einstein] an uninhibited opinion about his immediate circle. During one such
open phase during our conversation, I told him his environment in America and
asked, ’Who are your friends in this small town?’ He replied […] I do not
socialize because social encounters would distract me from my work and I
really only live for that, and it would shorten even further my very limited
lifespan. I do not have any close friends here as I had in my youth or later
in Berlin with whom I could talk and unburden myself. That may be due to my
age. I often have the feeling as if God has forgotten me here.

In his lecture “Scientific talent and autism: is there a connection?”, Baron-
Cohen merely repeats the arguments put forward in his previous text 555In the
case of Einstein, says Baron-Cohen,  ”if you look at his childhood, he is
described as being alone, having no friends, and not being interested in
mixing and socializing. Apparently, he was late to talk, a language delay.
Apocryphally he didn’t speak until he was five years old. And even then, when
he did start to speak, his speech showed echolalia. And as an adult and as a
distinguished scientist, he said: ‘I do not socialize because that would
distract me from my work, and I really only live for that.’ and adds [4]:

> So he wanted to be away from people and to only focus (some people would say
> obsessionally) on the world of physics, and he also had a strong interest in
> music when he wasn’t doing physics. And he said: ‘Music is a way for me to
> be independent of people.’ So you can see that this was a man who didn’t
> want to spend time socializing and instead wanted to focus on physics and
> music.

Again, Baron-Cohen cherry-picks quotations from Highfield and Carter [20] and
Michelmore [29].666The quotation: ”[…] music is a way for me to be independent
of people” was taken from Michelmore [29]:  Einstein worked alone now, so
music was the only way to get close to him. That was how Manfred Clynes
”reached” Einstein. […] Helen Dukas called to invite me [Cylnes] to supper.
[…] Einstein himself was rather jovial. Over the meal of meat and vegetables
and for two hours afterward, we talked about music. He told me it was as
important for him to improvise on the piano as it was for him to work on his
physics. ’It is a way for me to be independent of people,’ he said. ’And this
is highly necessary for the kind of society in which we have.’

Barbara Wolff – who had a long tenure at the Albert Einstein Archives and is
an editor in the Einstein Papers Project – and Hananya Goodman write [40]:

> Some of the characterizations of AS [Asperger’s syndrome] described in the
> paragraph above actually apply well to the young Albert as we know him from
> Maja’s and Max Talmey’s recollections.
>
> Both Maja and Talmey describe a boy who took little interest in boisterous
> games and, in general, in his peers, a boy who would concentrate patiently
> on elaborate constructions with building blocks or playing cards, delve into
> books and tricky arithmetic problems or play the violin. A sort of glass
> pane, as he called it many years later, separated him from his fellow human
> beings. Had such ”social phobia” then been classified as a personality
> disorder, and had his parents and doctors felt the need to ‘heal’ the boy by
> making him conform to some norm, Albert might not have become Einstein.

It seems that Wolff and Goodman agree with Baron-Cohen because, according to
the latter, Albert has become Einstein because he is an Asperger.

##  3 Historians object to diagnosing Einstein with autism

I think we cannot diagnose a dead person. Historians of science and medicine
have fiercely objected to Baron-Cohen’s retrospective diagnosis and have
generally leveled criticism at clinicians, psychologists, and non-experts for
retrospectively diagnosing disorders and diseases in deceased scientists.
Below I provide the major objections made by historians:

1\. Historians argue that people sometimes draw on dubious sources to make
retrospective diagnoses [26]. For instance, Daniela Caruso, professor of law
from Boston University, diagnosed Einstein with Asperger’s syndrome based on a
children’s book. She writes [8]:

> Post-mortem diagnoses are doubtful, but Albert Einstein’s life story, which
> begins with tales of delayed speech and abysmal performance at school,
> suggests that the most accomplished scientist of all time might have
> suffered from Asperger-like symptoms.

Caruso refers in a footnote to: “Don Brown, _Odd Boy Out: Young Albert
Einstein_ (2004)” [8]. _Odd Boy Out: Young Albert Einstein_ is a children’s
book by Don Brown.

I am disappointed with the cheapening of history.

2\. The retrospective diagnosis is a hobby of clinicians interested in history
who enjoy testing their diagnostic acumen on famous historical figures. The
physicians base their diagnosis on scant evidence, usually described in a non-
medical context. They uncover intriguing medical secrets in reports that
belong to an accessory section for incidental topics or letters to the editor
in medical journals. This practice raises ethical issues; in particular, the
dead scientists cannot say no. Retro-diagnosis can expose personal details
that no one in Einstein’s time could have known or understood. The
retrospective diagnoses could pose ethical problems or questions that, if
revealed, may cause harm to the scientist’s living descendants and relatives.
The diagnosing physicians strongly violate the principles of the medical
profession because they give their retrospective opinion on a patient they
have never seen nor examined [31], [26], [25].

Baron-Cohen replied to the above criticism in his lecture “Scientific talent
and autism: is there a connection?” [4]:

> This biographical approach is very interesting, but […] I’ve suggested that
> this might be a very unreliable way to approach the question because
> biographies are always fragmented. We only have partial information about
> what the person was like, information that has survived historically. The
> person isn’t here to speak up for themselves, so we don’t really know
> whether, if we saw them today alive, they would meet the criteria of autism
> or Asperger’s syndrome. But certainly, it’s pointing at the connection
> between great scientific talents and autism or Asperger’s”.

There are two problems here: the first problem is the impossibility of
verifying or falsifying the retrospective diagnosis for obvious reasons: we
cannot examine and test the historical subject. And the second problem is
ethical: publishing a diagnosis of a patient with whom the medical expert
never had a physician-patient relationship and without consent.

One could argue that historical celebrities are immune from privacy protection
because their lives are open to the public. And because they are long dead,
the subject of any potential harm no longer exists. But certain defenders of
the celebrity’s image and descendants of the historical figure might object to
the publication of a diagnosis that potentially stains the reputation of the
historical figure [31].

John Stachel gave a name to people who care about Einstein’s legacy (what he
considered as the staunchest defenders of his reputation); he called them
”keepers of the flame”.777Stachel writes in his book, _Einstein From ’B’ to
’Z’_ : ”I soon became aware of another peril involving loss of boundaries: the
danger of becoming a ‘keeper of the flame’ rather than a seeker of the truth.”
[37]

As a result of criticism, Baron-Cohen admitted there was a problem diagnosing
a person after his death because one needs the person’s consent. In his 2020
book, _The Pattern Seekers: A New Theory of Human Invention_ , Baron-Cohen
attenuates his argument [5]:

> “Some hyper-systemizers,888Hyper-systemizing is part of the cognitive style
> of autistic people. [6] in a range of fields, have been described [by the
> mathematician Ioan Mackenzie James from Oxford University] as autistic. For
> example, […] Albert Einstein and Henry Cavendish in the field of physics
> have all been described [by James] as autistic. In my view, it is unhelpful
> to speculate if someone – living or not – might be autistic, since a
> diagnosis is only useful if the person is seeking help and is struggling to
> function. Diagnosing someone – living or not – on the basis of fragmentary
> biographical information is unreliable and arguably unethical since
> diagnosis should always include the consent of the person and be initiated
> by them. And from a scientific perspective, hyper-systemizing does not
> automatically mean you’re autistic”.

Indeed, on January 17, 1927, Hugo Freund wrote to Einstein to ask if he would
allow himself to be psychoanalyzed ([12], Doc. 457). It is not known if an
answer was sent, but on the letter, in German in Einstein’s handwriting, there
is the following draft of a reply [12], Doc. 458; [14]: “I am sorry not to be
able to comply with your request, as I would very much like to remain in the
darkness of not having been analyzed.” In other words, Einstein refused to be
diagnosed and psychologically analyzed. Notwithstanding that, Baron-Cohen and
others have retrospectively diagnosed Einstein.

But in the above text, Baron-Cohen tries to shrug off the diagnosis of
Einstein with Asperger’s syndrome, saying that James described Einstein and
others as autistic. In 2012, Baron-Cohen went so far as to publish a paper
with several Cambridge University students having Asperger’s syndrome and
write: “Einstein, Mozart, Newton, Wittgenstein, and others (predominately
male, white, and deceased) are identified posthumously with AS and brilliance”
[19]. This sentence is disturbing because it insinuates that the brilliant
people are predominantly white males. Baron-Cohen and his students intertwine
two diagnoses - Asperger’s syndrome and brilliance - into white males.

3\. Let us move on to the third argument. Historical diseases and conditions
must be interpreted in their historical context. Retrospective diagnosis is
anachronistic because people try to diagnose a disease or disorder of the past
in contemporary terms. This is called ”anachronistic diagnosis.” Critics of
clinicians making retro-diagnosis say this kind of diagnosis can be
misleading.

First, medical experts arrive at a diagnosis of a historical figure using
modern diagnostic criteria; they reason that if historical figures had all
these symptoms, then they could have had these specific conditions. But in the
past, people had different habits and lifestyles than we do [31]. Hence, we
should investigate social diagnosis, i.e., the name that people in the past
allocated to a condition [13]. If the social circumstances allowing us to
perceive autism did not exist before some point relatively early in the
twentieth century, then to what extent can we say the condition existed
previously? [28]

Second, medical knowledge itself changes over time. Writing historical papers
on famous patients is problematic because clinicians regard the level of
scientific knowledge at the time of writing but assess the course of an
illness in the past.999For instance, the historical figure, Polish composer
Frédéric Chopin was first (1899) diagnosed as having tuberculosis; then, in
1961, allergic conditions and valvular stenosis were offered as a better
explanation for his condition. In 1987 he was diagnosed with cystic fibrosis;
in 1994, other genetic defects were suggested, such as alpha-1-antitrypsin-
deficiency [25].

For example, Temple Grandin is diagnosed with autism and has a Ph.D. in animal
science. She concludes, “Einstein had many traits of an adult with mild
autism, or Asperger’s syndrome.” And [18]:

> As a child, Einstein had many of these traits. He did not learn to speak
> until he was three. In a letter to a mother of an autistic child, he
> admitted to not being able to learn to speak until late and that his parents
> had been worried about it.

This passage is anachronistic. How does Grandin know that both the child and
Einstein were autistic? Children were not yet diagnosed as autistic in
Einstein’s lifetime.

4\. Historians object to a retrospective diagnosis that does not provide new
medical knowledge. This is as opposed to research based on historical sources
that will help modern medical researchers understand the spread of diseases
around our planet during human evolution and help us plan for unexpected
health events. There are many good reasons to study diseases and disorders in
the past. For instance, epidemiological analysis of data from historical
smallpox outbreaks has helped appropriate authorities plan for possible
outbreaks in the future [30].

To this, clinicians have responded by saying that studying historical figures
might help to determine how prevalent autism was in previous generations [1].
But then historians try to rebut this claim - see objection 3.

Concerning autism in previous generations, let us return to Temple Grandin.
Grandin compares herself to Einstein: ”Like Einstein, I am motivated by the
search for intellectual truth.” She then further elucidates on this point
[18]:

> When he developed the theory of relativity, he imagined himself on a beam of
> light. His visual images were vaguer than mine, and he could decode them
> into mathematical formulas. My visual images are extremely vivid, but I am
> unable to make the connection with mathematical symbols. Einstein’s
> calculation abilities were not phenomenal. He often made mistakes and was
> slow; but his genius lay in being able to connect visual and mathematical
> thinking. Einstein’s dress and hair were typical of an adult with autistic
> tendencies, most of whom have little regard for social niceties and rank.
> When he worked at the Swiss patent office, he sometimes wore green slippers
> with flowers on them”.

The above passage abounds in errors. But I nevertheless want to raise two
comments on this passage:

First, the people purporting to compare themselves to Einstein fail to mention
that his disheveled exterior reflected his inner humility. As he once said: ”I
speak to everyone in the same way, whether he is the garbage man or the
university president” [24]. This is typical of people with Asperger’s
syndrome, but by the same token, this behavior is also typical of humble
people. Hence, I suggest _not_ comparing yourself to Einstein if only for the
many things you don’t know about him. You can’t know everything about Einstein
because it is impossible to read _all_ the primary sources. And even if you
manage to read all that, many documents have gone missing, and there is always
hope of finding new lost letters, diaries, and manuscripts.

I will give you an example. Einstein once told Salaman: “Very few women are
creative. I should not have sent a daughter of mine to study physics. I’m glad
my wife doesn’t know any science, although my first wife did.” Grandin (a
female scholar), do you still want to compare yourself to Einstein? This might
be a slip of the tongue because Einstein admired several women and female
physicists and mathematicians of his time, e.g., the brilliant genius
physicist Marie Curie and genius mathematician Emmy Noether. Over the years,
Einstein made different statements that depended on the people he spoke with.
He would say one thing in the presence of distinguished scientists,
cooperating in tributes without questioning the narratives, and would say
quite the opposite on other occasions. Thus, I would be extremely careful when
comparing someone to Einstein.

Second, after Einstein’s rise to fame, Max Flückiger wrote in his book
_Einstein in Bern_ that Einstein often appeared in green slippers trimmed with
flowers at work. The patent office officials called him ”The man with the
green slippers.” A colleague also recalled that Einstein showed up at the
patent office one day with a saw and proceeded to shorten the legs of his
chair because it was not adjustable and was too high for him [17]. Abraham
Pais described Flückiger’s book as containing several reproductions of rare
documents about Einstein’s younger days. But ”The text contains numerous
inaccuracies” [32]. In other words, Flückiger concocted the above stories out
of things that never happened.

5\. Historians argue that it is often unclear how a highly specific diagnosis
would make any difference in the scholarship of the historical figure in
question [31]. It is asked: what is the objective of retrospectively
diagnosing Einstein? What goals does it serve? What justifies the
retrospective diagnosis of historical figures? What is the reason modern
researchers retrospectively diagnose a historical figure as autistic? Does the
diagnosis of Einstein as autistic deliver new medical insight into autism?
Does it help us understand how Einstein created the theory of relativity and
how he arrived at his significant discoveries?

Ioan James writes [23]: ”In the case of Einstein, we can conclude that he did
have Asperger’s syndrome.” James has further stated: ”Although it seems to be
widely accepted that Einstein had the syndrome, none of the many detailed
biographies mentions this” [22]. First, such a diagnosis does not make any
difference in the scholarship of Einstein and the pathway to his theories.
Second, not only do none of the ”biographies mention this,” several
biographies even try to denounce it, as I show in the next section, claiming
it is an utter myth.

##  4 Historians try to debunk myths about Einstein

It seems to me that in trying to debunk myths, some historians hobble the
narrative of extraordinary and creative scientists in that they extend the
life of other myths. The issue is that it is not so much that historians
endeavor to debunk myths that bothers me; it is how they do so.

Although historians’ critique of Baron-Cohen and others includes debunking
myths, it piggybacks on another myth: presenting Einstein as a dull,
conscientious, agreeable person and an industrious and socially adept
individual better suited to Thomas Kuhn’s incremental ”normal science.”

First, when I wrote my first book, I was told that Albert Einstein, his sister
Maja Winteler-Einstein, and the family members had exaggerated the story of
Albert, who developed slowly, learned to talk late, and whose parents thought
something was wrong with him. I was further told that, of course, there is no
doubt that these stories have a grain of truth, and Maja and Albert recount
their recollections in all sincerity, but these stories sound like family
tales and may be exaggerated. Moreover, Einstein’s friends and assistants (in
interviews and correspondences) contributed to spreading this myth. They thus
inspired biographers to create a widespread mythical public image of Albert
Einstein that embodies stories about Einstein, ”the retarded genius.”

We first conjecture that Einstein and his family members had exaggerated the
story of Albert, ”the retarded genius,” and then show that the ”real” Albert
was a different matter. For instance, Albert’s mother recognized that her son
was talented, and it does not seem that she thought he would develop into some
eccentric. But seen from a distance of time, almost ten years after writing my
book [38], the above argument sounds improbable because Einstein and his
family are accused of inventing stories to create a myth that serves a
specific purpose.

A different way of considering the situation is presenting Einstein as having
a special gift of friendship. He may not have been working with a large group
of scientists. Still, he was deeply embedded in the academic community and was
a modern professional scientist who earned his living through his work as a
professor at the university. Historians debunk myths by saying that Einstein
was not an isolated genius ”working by himself in an attic with pen and paper”
[16]. Einstein had close friendships with physicists and a special gift of
collegiality and was very well-adjusted. Then the argument goes on like this.
Although Einstein was sometimes rude or insensitive, he was not unlike many
individuals. Some of his social behaviors and attitudes may seem
unconventional today, but they were not unusual in his day and milieu. He was
very sociable and was emotionally involved with friends and family, even if he
savored solitude when it was within his reach to pursue his science
[7].101010I would like to correct some of the stigmas and prejudices about
Asperger’s syndrome found in _An Einstein Encyclopedia_. Asperger’s syndrome
(autism) is neither a disease nor a mental or emotional disorder. Asperger’s
syndrome (autism) is also not a disorder people ”suffer” from. Asperger’s
syndrome is _not_ any of the following: a defect, developmental anomaly,
pathological conduct, a mental illness, schizophrenia, and bouts of severe
depression.

In his biography of Einstein, _His Life and Universe_ , Walter Issaacson
elucidates why he is not convinced of the diagnosis of Einstein with
Asperger’s syndrome: ”Even as a teenager, Einstein made close friends, had
passionate relationships, enjoyed collegial discussions, communicated well
verbally, and could empathize with friends and humanity in general” [21].
111111Issacson writes: ”A Google search of Einstein + Asperger’s results in
$146,000$ pages. I do not find such a long distance diagnosis to be
convincing” [21]. I did the exact search, and I found only $25$ pages. Still,
it does not mean that these $25$ pages are convincing.

In my opinion, the above narrative, very unfortunately, strips off Einstein
from his great sense of humor, from being stubborn and unconventional and
sticking out his tongue at his pursuers to express his annoyance (the
photograph that has been reproduced endlessly).

Einstein’s former Cantonal School classmate, Hans Byland, one year older than
Einstein, had painted a verbal portrait of Einstein as a teenager: Einstein as
a young man could not be fitted into any pattern, an impudent Swabian, a
restless spirit; nothing escaped the sharp gaze of his large bright brown
eyes. ”A sarcastic curl of his rather full mouth with the protruding lower lip
did not encourage Philistines to fraternize with him.” His attitude towards
the world was that of a laughing philosopher, and his witty mockery pitilessly
lashed out at any conceit or pose. Einstein made no bones about voicing his
personal opinions, whether offensive or not, and he had courageous adherence
to the truth [36]. Of course, one can call this ”communicated well verbally.”
We have Einstein’s rude letter in which he lashed out at the editor of _The
Physical Review_ : ”We (Mr. Rosen and I) had sent you our manuscript for
publication and had not authorized you to show it to specialists before it was
printed. I see no reason to address your anonymous expert’s – in any case,
erroneous – comments. Based on this incident, I prefer to publish the paper
elsewhere” [27]. And Einstein attacked his opponents at the Hebrew University
and termed Judah Leon Magnes and his supporters “downright vermin.” On another
occasion, he called the university a “bug-infested house” [34]. It, therefore,
seems that Einstein made no bones about voicing his opinions, whether
offensive or not.

It seems to me that the supporters of the view of Einstein as a very well-
adjusted individual not only fail in demolishing myths, this narrative
repudiates Einstein’s patent office years. Einstein’s friends and colleagues
at the patent office, his table and drawer, pen and sheets of paper, and
especially the thoughts he hatched there were antipodal to an academic
community.

Einstein later wrote that, unlike himself, Marcel Grossmann ”was not a
vagabond and loner”[15]. Einstein wrote to Mileva Marić: “I always find that I
am in the best company when I am alone, except when I am with you” [10]
(Einstein to Marić, Doc 128, Dec 17, 1901). Indeed, unlike Einstein, Grossmann
was quickly given an assistant post under Prof. Wilhelm Fiedler; Grossmann
succeeded Fiedler as a professor at the Polytechnic in 1907. On the other
hand, three years after the publication of the miraculous year papers –
special relativity, $E=mc^{2}$ first paper, quanta and Brownian motion – Jakob
Laub wrote to Einstein, ”I must confess to you that I was surprised to read
that you have to sit in an office for eight hours a day. But, history is full
of bad jokes” (Laub to Einstein, [11], Doc. 91, March 1, 1908).

Suppose Einstein had this unique quality of being well-adjusted and deeply
embedded in the academic community, as purported. Why did he sit in the patent
office for so long? None of this makes sense in the picture of the well-
adjusted and embedded-in-the-science-community Einstein. A narrative of a
socially adept Einstein does not even make sense in the context of the later
Einstein, sitting in his office in Princeton, let alone sitting in the patent
office.

We are trying to press a conscientious and agreeable Einstein into a
rebellious Einstein. But we don’t need Karl Popper to tell us that Einstein
was one of the most exciting and imaginative scientists ever to live; he was
intelligent and creative, a vocational revolutionary scientist. And this is of
utmost importance. He was brilliant, inspirational, abrasive, and rebellious,
precisely the type of truth-seeker to create a scientific revolution.
121212See the discussion in [9].

Einstein thought that certain personal matters of his life should not be made
public. That is the reason he did not like biographies that dealt too much
with his personal life [38]. But private letters are profusely found in the
_Collected Papers of Albert Einstein_ (_CPAE_); for instance, Einstein’s love
letters to his first wife, Mileva Marić; Einstein’s later correspondence with
Marić and his two sons, Hans Albert, and Eduard; Einstein’s exchange of
letters with his second wife and first cousin, Elsa Lowenthal Einstein;
correspondence with Einstein’s sister, Maja; letters Einstein wrote to his
extra-marital lover Betty Neumann, etc. The reasons behind the decision to
publish Einstein’s private correspondence are that Einstein is not a private
person anymore; his life is open to the public. Einstein has ceased being a
private individual and belongs to history. Since Einstein is long dead,
publishing his letters cannot cause him any harm. On the contrary, he is a
historical scientist in the same category as Newton and Galileo. We do not
think of the privacy of such historical figures. We want to know as much as we
can about them because, without full knowledge, one cannot fully understand
the evolution of their ideas [2].

But then, based on Einstein’s private correspondence, biography of his sister
Maja (an abridged version of which was published in the _CPAE_), and other
first-hand evidence, people have written biographies and books on Einstein’s
private life. And based on these books, other people, in turn, are
retrospectively diagnosing Einstein with all sorts of things. Historians who
care about Einstein’s legacy then fiercely object to this abuse of Einstein’s
privacy and, in turn, engage in (futile) efforts to protect his privacy.
Hence, we have vicious circularity.

## Acknowledgement

This work is supported by ERC advanced grant number 834735.

## References

  * [1] E. L. Altschuler (2013). ”Asperger’s in the Holmes Family.” _Journal of Autism and Developmental Disorders_ 43, pp. 2238–2239.
  * [2] A. S. Bailey (1989). ”On the Collected Papers of Albert Einstein: The Development of the Project.” _Proceedings of the American Philosophical Society_ 133, pp. 347-359.
  * [3] S. Baron-Cohen (2003). _Male and Female Brains and the Truth about Autism. The Essential Difference_. New York: Basic Books.
  * [4] S. Baron-Cohen (2011). “Scientific Talent and Autism.” Lecture.
  * [5] S. Baron-Cohen (2020) _The Pattern Seekers: How Autism Drives Human Invention_. New York: Basic Books.
  * [6] S. Baron-Cohen, E. Ashwin, C. Ashwin, T. Tavassoli, and B. Chakrabarti (2009). “Talent in autism: hyper-systemizing, hyper-attention to detail and sensory hypersensitivity.” _Philosophical Transactions of the Royal Society B: Biological Sciences_ 364, pp. 1377–1383.
  * [7] A. Calaprice, D. Kennefick, and R. Schulmann (2016). _An Einstein Encyclopedia_. Princeton: Princeton University Press.
  * [8] D. Caruso (2010). “Autism in the U.S.: Social Movement and the Legal Change.” _American Journal of Law and Medicine_ 36, pp. 483-539.
  * [9] B. G. Charlton (2009). ”Why are modern scientists so dull? How science selects for perseverance and sociability at the expense of intelligence and creativity.” _Medical Hypothesis_ 72, pp. 237-243.
  * [10] _Collected Papers of Albert Einstein. Volume 1: The Early Years, 1879–1902_. J. Stachel, D. C. Cassidy, and R. Schulmann (eds.). Princeton: Princeton University Press, 1987.
  * [11] _Collected Papers of Albert Einstein. Volume 5: The Swiss Years: Correspondence, 1902–1914_. M. J. Klein, A. J. Kox, and R. Schulmann (eds.). Princeton: Princeton University Press, 1993.
  * [12] _Collected papers of Albert Einstein. Volume 15: The Berlin Years: Writings and Correspondence, June 1925-May 1927_. D. Kormos Buchwald, J. Illy, A. J. Kox, D. Lehmkuhl, Z. Rosenkranz and J. Nollar James (eds.). Princeton: Princeton University Press, 2018.
  * [13] A. Cunningham (2002). ”Identifying disease in the past: cutting the Gordian knot.” _Asclepio_ 54, pp. 13–34.
  * [14] H. Dukas and B. Hoffmann (1979). _The Human Side. New Glimpses from his Archives_. Princeton: Princeton University Press.
  * [15] A. Einstein (1955). ”Autobiographische Skizze.” In C. Seelig (1956). _Helle Zeit – Dunkle Zeit. In memoriam Albert Einstein_. Zurich: Braunschweig: Friedrich Vieweg und Sohn/Europa.
  * [16] K. Fesenmaier (2014).”Einstein Online: An Interview with Diana Kormos-Buchwald,” _Caltech_.
  * [17] M. Flückiger (1974). _Albert Einstein in Bern_. Switzerland: Verlag Paul Haupt Bern.
  * [18] T. Grandin (1995). _Thinking in Pictures: My Life with Autism_. New York: Vintage Books.
  * [19] J. Hastwell, N. Martin, S. Baron-Cohen, and J. Hardling (2012). “Giving Cambridge University students with Asperger syndrome a voice: a qualitative, interview-based study towards developing a model of best practice.” _Good Autism Practice_ 13, pp. 56-63.
  * [20] R. Highfield and P. Carter (1994). _The Private Lives of Albert Einstein_. New York: St. Martin’s Press.
  * [21] W. Issacson (2007). _His Life and Universe_. New York: Simon $\&$ Schuster.
  * [22] I. M. James (2003). “Singular scientists.” _Journal of the Royal Society of Medicine_ 96, pp. 36–39.
  * [23] I. M. James (2006). _Asperger’s Syndrome and High Achievement: Some Very Remarkable People_. London: Jessica Kingsley Publishers.
  * [24] F. Jerome and R. Taylor (2006). _Einstein on Race and Racism_. New Jersey: Rutgers University Press.
  * [25] A. Karenberg (2009). ”Retrospective Diagnosis: Use and Abuse in Medical Historiography.” _Prague Medical Report_ 110, pp. 140–145.
  * [26] S. Kean (2012). ”Retrodiagnoses. Investigating the ills of long-dead celebrities”. _Science_ 337, pp. 30–31.
  * [27] D. Kennefick (2005). ”Einstein versus the Physical Review.” _Physics Today_ 58, pp. 43-48.
  * [28] P. McDonagh (2008). “Autism and Modernism. A Genealogical Exploration.” In M. Osteen (ed.). _Autism and Representation_ , pp. 99-116.
  * [29] P. Michelmore (1962). _Einstein, Profile of the Man_. New York: Dodd, Mead $\&$ Company.
  * [30] P. D. Mitchell (2011). ”Retrospective diagnosis and the use of historical texts for investigating disease in the past.” _International Journal of Paleopathology_ 1, pp. 81–88.
  * [31] O. Muramoto (2014). ”Retrospective diagnosis of a famous historical figure: ontological, epistemic, and ethical considerations.” _Philosophy, Ethics, and Humanities in Medicine_ 9, pp. 1-15.
  * [32] A. Pais (1982). _Subtle is the Lord. The Science and Life of Albert Einstein_. Oxford: Oxford University Press.
  * [33] J. Plesch and P. H. Plesch (1955). “Some Reminiscences of Albert Einstein.” _Notes and Records of the Royal Society of London_ 49, pp. 303-328.
  * [34] Z. Rosenkranz (2011). _Einstein Before Israel: Zionist Icon or Iconoclast?_ Princeton: Princeton University Press.
  * [35] E. Salaman (1955) “A Talk With Einstein.” _The Listener_ 54, pp. 370-371.
  * [36] C. Seelig (1956). _Albert Einstein: A Documentary Biography_. Translated to English by Mervyn Savill. London: Staples Press. (1954). _Albert Einstein. Eine dokumentarische Biographie_. Zurich: Europa Verlag.
  * [37] J. Stachel (2002). _Einstein From ’B’ to ’Z’_. Boston: Birkhäuser.
  * [38] G. Weinstein (2015). General Relativity Conflict and Rivalries: Einstein’s Polemics with Physicists (Newcastle, UK: Cambridge Scholars Publishing).
  * [39] M. Winteler-Einstein (1924). _Albert Einstein – A Biographical Sketch_. _Beitrag für sein Lebensbild_._Collected Papers of Albert Einstein. Vol. 1: The Early Years,1879–1902_. J. Stachel, D. Cassidy, and R. Schulmann (eds.). Princeton: Princeton University Press, 1987, pp. xv-xxii. (pp. xlviii-lxvi.)
  * [40] B. Wolff and H. Goodman (2001). “The Legend of the Dull-Witted Child Who Grew Up to Be a Genius.” _The Albert Einstein Archives_ The Hebrew University of Jerusalem.


satisfiability checking, we restrict to the case without optional game solving
for the sake of simplicity.)

######  Proof 4.3.

The loop of the algorithm expands the determinized and complemented tracking
automaton node by node and hence is executed at most
$|D_{\chi}|\in\mathcal{O}((n_{0}k)!^{2})$ times. A single expansion step can
be implemented in time $\mathcal{O}(2^{n_{0}})$ since in both propositional
and modal expansion steps, at most $2^{n_{0}}$ new nodes are added,
corresponding to the maximal possible number of choice functions and matching
selections, respectively. By Lemma 31, the final propagation step can be
performed by computing a fixpoint of nesting depth $2n_{0}k$ of the function
$f$ over $\mathcal{P}(D_{\chi})^{2n_{0}k}$. A single computation of
$f(\mathbf{X})$ for a tuple $\mathbf{X}\in\mathcal{P}(D_{\chi})^{2n_{0}k}$ can
be implemented in time
$\mathcal{O}(|D_{\chi}|\cdot(t(n_{0})+2^{n_{0}}))=\mathcal{O}((n_{0}k)!^{2}\cdot(t(n_{0})+2^{n_{0}}))$
by going through all elements $q$ of $D_{\chi}$, calling the one-step
satisfiability checker on $l^{A}(q)\cap\Lambda(\mathbf{F})$. Since we have
$2n_{0}k=\mathcal{O}(\log|D_{\chi}|)$, it follows from recent work on the
computation of nested fixpoints [HS21] that these fixpoints can be computed in
time $\mathcal{O}((n_{0}k)!^{2c}\cdot t(n_{0}))$, where $c=5$. (Classical
methods for computing nested fixpoints [LBC+94, Sei96] are exponential in the
nesting depth, which however still leads to a singly exponential overall time
bound, computed explicitly in the conference version of the paper [HS19].)
Thus the complexity of the whole algorithm is dominated by the complexity of
the final game solving step, and adheres to the claimed asymptotic bound.

Relying on the correctness proof found in Section 5 below, we obtain the
following results.

######  Corollary 33.

If the strict one-step satisfiability problem of a coalgebraic logic is in
ExpTime, then the satisfiability problem of the corresponding coalgebraic
$\mu$-calculus is in ExpTime.

Since as discussed in Remark 35, the existence of a tractable set of tableau
rules implies the required time bound on one-step satisfiability, the above
result subsumes earlier bounds obtained by tableau-based approaches in
[CKP11a, HSE16, HSD18]; however, it covers additional example logics for which
no suitable tableau rules are known. In particular, by Example 25, we have:

######  Proposition 34.

The satisfiability problems of the following logics are in ExpTime:

  1. (1)

the standard $\mu$-calculus,

  2. (2)

the graded $\mu$-calculus,

  3. (3)

the (two-valued) probabilistic $\mu$-calculus,

  4. (4)

the graded $\mu$-calculus with polynomial inequalities,

  5. (5)

the (two-valued) probabilistic $\mu$-calculus with polynomial inequalities.

######  Remark 35 (Modal tableau rules).

As indicated in the introduction, previous generic algorithms for the
coalgebraic $\mu$-calculus [CKP+11b] employ tractable sets of modal tableau
rules [SP09] in place of one-step satisfiability checking. This method roughly
works as follows. A _(monotone) modal tableau rule_ over a finite set $W$ of
propositional variables (local to the rule) has the form $\phi/\psi$ where
$\psi$ is a propositional formula over $W$, given in disjunctive normal form
as a subset of $\mathcal{P}(W)$, and $\phi$ is a finite subset of
$\Lambda(W)$, representing a finite conjunction, that mentions every variable
in $W$ exactly once. (Thus, rules are formally similar to one-step pairs, on
which the last requirement is also sometimes imposed as discussed in Remark
24.) Given a set $V$, a _rule match_ to a finite subset $\gamma$ of
$\Lambda(V)$ is a pair $(\phi/\psi,\sigma)$ consisting of a rule $\phi/\psi$
and a substitution $\sigma\colon W\to V$ that acts injectively on $\phi$ (i.e.
for $\heartsuit a,\heartsuit b\in\phi$, $\sigma(a)=\sigma(b)$ implies $a=b$)
such that $\phi\sigma\subseteq\gamma$, where we write application of the
substitution $\sigma$ in postfix notation. In the notation of the present
paper, a set $\mathcal{R}$ of modal tableau rules is _one-step tableau sound
and complete_ if the following condition holds for each one-step pair
$(\gamma,\Theta)$ over $V$: The pair $(\gamma,\Theta)$ is satisfiable iff
$\psi\sigma\cap\Theta\neq\emptyset$ for each rule match $(\phi/\psi,\sigma)$
as above to $\gamma$; note that applying the substitution $\sigma\colon W\to
V$ to $\psi\subseteq\mathcal{P}(W)$ yields a propositional formula
$\psi\sigma$ over $V$ that is represented as a subset of $\mathcal{P}(V)$.

A rule set $\mathcal{R}$ is _exponentially tractable_ if rule matches can be
encoded as strings in such a way that every rule match to a given finite set
$\gamma\subseteq\Lambda(V)$ has a code of polynomial size in
$\mathsf{size}(\gamma)$, and moreover (i) it can be decided in exponential
time whether a given code actually encodes a rule match to $\gamma$ and (ii)
the conclusion $\psi\sigma$ of a rule match $(\phi/\psi,\sigma)$ can be
computed from its code in exponential time. Using an exponentially tractable
rule set, we can decide the strict one-step satisfiability problem in
exponential time: Given a one-step pair $(\gamma,\Theta)$, go through all all
codes of possible rule matches, filtering for actual matches
$(\phi/\psi,\sigma)$, and check for each match that
$\psi\sigma\cap\Theta\neq\emptyset$. Thus, the present approach applies more
generally than the approach via modal tableau rules. See also [KPS22] for a
more detailed discussion of the relationship.

Tractable sets of tableau rules for the graded $\mu$-calculus and the
Presburger $\mu$-calculus have been claimed in previous work [SP09, KP10].
However, these rule sets have since turned out to be incomplete. Indeed the
rule sets are very similar to rule sets for real-valued systems, and remain
sound over an evident real-valued relaxation of the semantics, an observation
from which incompleteness is rather immediate. A concrete example for the
Presburger case is given in [KPS22, Remark 3.8].

######  Remark 36 (One-step satisfiability and fusion).

The criterion of Corollary 33 is stable under fusion of logics; that is:
Suppose that the strict one-step satisfiability problems for logics with
disjoint modal similarity types $\Lambda_{i}$ interpreted over functors
$F_{i}$, for $i=1,2$, are both in ExpTime. Then the strict one step
satisfiability problem of the fusion (Remark 4), with modal similarity type
$\Lambda=\Lambda_{1}\cup\Lambda_{2}$ interpreted over $F=F_{1}\times F_{2}$,
is in ExpTime as well. To see this, just note that a one-step pair
$(\gamma,\Theta)$ over $V$ in the fusion is satisfiable over $F=F_{1}\times
F_{2}$ iff for $i=1,2$. the one-step pair $(\gamma\cap\Lambda_{i}(V),\Theta)$
over $V$ is satisfiable over $F_{i}$.

Thus, we obtain by Corollary 33 that the satisfiability problem of any
combination of the logics mentioned in Proposition 34 is in ExpTime; for
instance, this holds for the logic of Markov decision processes described in
Example 2.6.

##  5\. Soundness and Completeness

We now prove the central result, that is, the correctness of the
satisfiability games presented in the previous section. Our program is as
follows: We identify an embodiment of a winning strategy of the existential
player in the satisfiability game $\mathsf{G}_{\chi}$ in the shape of a
graphical structure on a subset of the set $D_{\chi}$ of states of the co-
determinized tracking automaton $\mathsf{B}_{\chi}$, called a _tableau_ ;
specifically, this set consists of those automaton states that are won by the
existential player when considered as nodes of $\mathsf{G}_{\chi}$. We show on
the one hand that tableaux can indeed be extracted from winning strategies,
and that every tableau carries a coalgebra structure that is _coherent_ with
its graphical structure and its labels; such coalgebras then satisfy a truth
lemma saying that every state satisfies its label. This shows _completeness_.
For _soundness_ , we will show conversely that we can extract a winning
strategy in $\mathsf{G}_{\chi}$ from a given model of $\chi$.

######  Definition 37 (Pre-tableaux and tableaux).

Given a ternary relation $R\subseteq A\times B\times A$ and $a\in A$, $b\in
B$, $B^{\prime}\subseteq B$, we generally write $R(a,b)=\\{a^{\prime}\in
A\mid(a,b,a^{\prime})\in R\\}$, $R(a,B^{\prime})=\bigcup_{b\in
B^{\prime}}R(a,b)$ and $R(a)=R(a,B)$. A _pre-tableau_ $(W,L)$ _for $\chi$_
consists of a set $W\subseteq D_{\chi}$ of nodes and a transition relation
$L\subseteq W\times\Sigma\times W$ such that the following conditions hold:

  1. (1)

The initial node $q_{\mathsf{init}}$ of $\mathsf{B}_{\chi}$ is in $W$;

  2. (2)

the relation $L$ is a restriction of the transition function $\delta$ of
$\mathsf{B}_{\chi}$, i.e. $L(q,\sigma)\subseteq\\{\delta(q,\sigma)\\}$ for all
$q\in W$ and $\sigma\in\Sigma$ (so $L(q,\sigma)$ is either
$\\{\delta(q,\sigma)\\}$ or $\emptyset$);

  3. (3)

for all $q\in W$, we have
$[\\![l^{A}(q)\cap\Lambda(\mathbf{F})]\\!]^{l^{A}[L(q,\mathsf{selections})]}_{1}\neq\emptyset$
(i.e. the one-step pair
$(l^{A}(q)\cap\Lambda(\mathbf{F}),l^{A}[L(q,\mathsf{selections})])$ is
satisfiable); and

  4. (4)

for all $q\in W$, we have $\bot\notin l^{A}(q)$ and there is a unique
$\tau\in\mathsf{choices}$ such that $L(q,\tau)\neq\emptyset$ (so
$L(q,\mathsf{choices})=L(q,\tau)=\\{\delta(q,\tau)\\}$ by (2)).

An (infinite) _path_ through $(W,L)$ (_starting at_ $q_{0}$) is an infinite
sequence
$(q_{0},\sigma_{0}),(q_{1},\sigma_{1}),\ldots\in(W\times\Sigma)^{\omega}$ such
that $q_{i+1}\in L(q_{i},\sigma_{i})$ for all $i$. Transitions
$(q,\tau,q^{\prime})\in L$ such that $\tau\in\mathsf{choices}$ are _local
transitions_ , and transitions $(q,\kappa,q^{\prime})\in L$ such that
$\kappa\in\mathsf{selections}$ are _modal transitions_ ; a _local path_ is a
path that contains only local transitions. By the above conditions on local
transitions, there is, for every node $q$, a unique local path starting at
$q$, which we denote by $\pi(q)$. A _tableau_ is a pre-tableau in which every
path $(q_{0},\sigma_{0}),(q_{1},\sigma_{1}),\ldots$ through $(W,L)$ starting
at $q_{0}=q_{\mathsf{init}}$ is _accepted_ by $\mathsf{B}_{\chi}$ in the sense
that the word $\sigma_{0},\sigma_{1},\ldots$ is in $L(\mathsf{B}_{\chi})$.

As indicated above, winning strategies for the existential player in the
satisfiability game (Definition 28) induce tableaux:

######  Lemma 38.

If the existential player wins the satisfiability game $\mathsf{G}_{\chi}$,
then there is a tableau for $\chi$.

######  Proof 5.1.

Let $\mathsf{win}^{\exists}$ be the winning region of the existential player
in $\mathsf{G}_{\chi}$, let $s\colon V_{\exists}\to V$ be a _history-free_
strategy for the existential player that wins all nodes in
$\mathsf{win}^{\exists}$, and put $W=\mathsf{win}^{\exists}\cap D_{\chi}$. By
assumption, $q_{\mathsf{init}}\in W$. We then define $L\subseteq
W\times\Sigma\times W$ as follows. Let $q\in W$. By the definition of the
satisfiability game, $s(q,0)$ has the form $s(q,0)=\delta(q,\tau)$ where
$\tau\in\mathsf{choices}$; we then put $L(q,\tau)=\\{\delta(q,\tau)\\}$, and
$L(q,\tau^{\prime})=\emptyset$ for all other
$\tau^{\prime}\in\mathsf{choices}$. Similarly, $s(q,1)$ has the form
$s(q,1)=(q,\Xi)$ where $\Xi\in\mathcal{P}(\mathsf{selections})$, and we put
$L(q,\kappa)=\\{\delta(q,\kappa)\\}$ if $\kappa\in\Xi$, and
$L(q,\kappa)=\emptyset$ otherwise. Then $(W,L)$ is a pre-tableau by
construction. To show that $(W,L)$ is a tableau, let
$(q_{0}=q_{\mathsf{init}},\sigma_{0}),(q_{1},\sigma_{1}),\ldots$ be a path in
$(W,L)$. By construction of $(W,L)$, this path induces a play in
$\mathsf{G}_{\chi}$ that follows $s$ (explicitly, if
$\sigma_{i}\in\mathsf{choices}$, then the play has one intermediate node
$(q_{i},0)$ between $q_{i}$ and $q_{i+1}=s(q_{i},0)$, and if
$\sigma_{i}\in\mathsf{selections}$, then the play has two intermediate nodes
$(q_{i},1)$ and $s(q_{i},1)$ between $q_{i}$ and $q_{i+1}$). Since $s$ is a
winning strategy, the word $\sigma_{0},\sigma_{1},\ldots$ is accepted by
$\mathsf{B}_{\chi}$ with accepting run $q_{\mathsf{init}},q_{1},\ldots$,
showing that $(W,L)$ is a tableau.

We proceed to construct a coalgebraic model of the target formula $\chi$ on a
tableau for $\chi$. As indicated above, the key property of such a coalgebra
is _coherence_ w.r.t. the tableau:

######  Definition 39.

Let $(W,L)$ be a pre-tableau. We define the _cumulative labeling function_
$l^{A}_{+}:W\to\mathcal{P}(\mathbf{F})$ by

$\displaystyle l^{A}_{+}(q)=\bigcup\\{l^{A}(q^{\prime})\mid
q^{\prime}\in\pi(q)\\},$

that is, $l^{A}_{+}(q)$ is the union of the labels of all nodes on the local
path $\pi(q)$ that starts at $q$. A node $q\in W$ is a _state node_ if
$l^{A}(q)\cap\Lambda(\mathbf{F})=l^{A}_{+}(q)\cap\Lambda(\mathbf{F})$, that
is, if $q$ already contains all modal literals that are contained in the label
of some node on the local path $\pi(q)$ (note that the set of modal literals
contained in the label grows monotonically along $\pi(q)$). We denote the set
of state nodes of $(W,L)$ by $\mathsf{states}(W,L)\subseteq W$. For $q\in W$,
we let $\lceil v\rceil$ denote the first state node (for definiteness) on
$\pi(q)$ (possibly $\lceil q\rceil=q$), and extend this notation to sets of
nodes, putting $\lceil V\rceil=\\{\lceil q\rceil\mid q\in
V\\}\subseteq\mathsf{states}(W,L)$ for $V\subseteq W$. Furthermore, we define
the _pseudo-extension_ $\widehat{[\\![\psi]\\!]}$ of a formula
$\psi\in\mathbf{F}$ to be the set of state nodes $q$ for which there is some
node $u$ such that $q=\lceil u\rceil$ and such that the cumulative label of
$u$ contains $\psi$:

$\displaystyle\widehat{[\\![\psi]\\!]}$ $\displaystyle=\\{\lceil
u\rceil\in\mathsf{states}(W,L)\mid\psi\in l^{A}_{+}(u)\\}$

######  Remark 40.

Observe that starting from a non-state node $q$ in a pre-tableau, the labels
of nodes along the local path $\pi(q)$ become semantically stronger through
the choice of disjuncts in disjunctions, until the state node $\lceil q\rceil$
is reached. At the same time, formulae may be syntactically lost from the
label along steps of the local path; e.g. a disjunction may be replaced with a
disjunct, a conjunction with both its conjuncts, and fixpoint literals may be
unfolded. The cumulative label serves essentially as a convenient way of
dealing with these phenomena, avoiding the need to speak about a notion of
non-modal entailment that combines propositional entailment and fixpoint
unfolding.

######  Definition 41 (Coherence).

Let $(W,L)$ be a pre-tableau. A coalgebra structure $\xi$ on
$\mathsf{states}(W,L)$ is _coherent_ (over $(W,L)$) if for all
$q\in\mathsf{states}(W,L)$ and all $\heartsuit\psi\in\mathbf{F}$,

$\displaystyle q\in\widehat{[\\![\heartsuit\psi]\\!]}\text{ implies
}\xi(q)\in[\\![\heartsuit]\\!](\widehat{[\\![\psi]\\!]}\cap\lceil
L(q,\mathsf{selections})\rceil).$

######  Lemma 42 (Existence lemma).

Let $(W,L)$ be a pre-tableau. Then there is a coherent coalgebra structure on
$(\mathsf{states}(W,L),\xi)$.

######  Proof 5.2.

Let $q\in\mathsf{states}(W,L)$ be a state node. As $(W,L)$ is a pre-tableau,
we have
$[\\![l^{A}(q)\cap\Lambda(\mathbf{F})]\\!]_{1}^{l^{A}[L(q,\mathsf{selections})]}\neq\emptyset$;
so pick
$t\in[\\![l^{A}(q)\cap\Lambda(\mathbf{F})]\\!]_{1}^{l^{A}[L(q,\mathsf{selections})]}$
and put $\xi(q)=(Fg)(t)$, where $g(u)=\lceil h(u)\rceil$ for some section $h$
of $l^{A}\colon L(q,\mathsf{selections})\to l^{A}[L(q,\mathsf{selections})]$.
We show that this choice of $\xi$ is coherent: Let
$q\in\widehat{[\\![\heartsuit\psi]\\!]}$, i.e. $\heartsuit\psi\in
l^{A}(q)=l^{A}_{+}(q)$. By construction, we have
$t\in[\\![\heartsuit]\\!]\\{l^{A}(u)\mid u\in L(q,\mathsf{selections}),\psi\in
l^{A}(u)\\}$ and

$\displaystyle\\{l^{A}(u)\mid u\in L(q,\mathsf{selections}),\psi\in
l^{A}(u)\\}\subseteq g^{-1}[\widehat{[\\![\psi]\\!]}\cap\lceil
L(q,\mathsf{selections})\rceil]$

By monotonicity and naturality of predicate liftings, we hence have

$\displaystyle\xi(q)=(Fg)(t)\in[\\![\heartsuit]\\!](\widehat{[\\![\psi]\\!]}\cap\lceil
L(q,\mathsf{selections})\rceil),$

as required.

We finally show that a coherent coalgebra structure is indeed a model of
$\chi$, and more generally that pseudo-satisfaction implies actual
satisfaction:

######  Lemma 43 (Truth lemma).

Let $(W,L)$ be a tableau, and let $\xi$ be a coherent coalgebra structure on
$V:=\mathsf{states}(W,L)$. Then for all $\psi\in\mathbf{F}$,

$\displaystyle\widehat{[\\![\psi]\\!]}\subseteq[\\![\psi]\\!]$

in $(V,\xi)$.

######  Proof 5.3.

By Lemma 21, it suffices to show that for all $\psi\in\mathbf{F}$ and all
$q\in\widehat{[\\![\psi]\\!]}$, the existential player wins the node
$(q,\psi)$ in the model checking game $\mathsf{G}_{{\chi,(V,\xi)}}$. We define
a history-free strategy $s$ for the existential player in
$\mathsf{G}_{{\chi,(V,\xi)}}$ as follows. Let $\psi\in\mathbf{F}_{\exists}$
and $q\in\widehat{[\\![\psi]\\!]}$. We distinguish cases on the shape of
$\psi$:

  1. (1)

$\psi=\bot$: By the definition of pre-tableaux, this case does not occur.

  2. (2)

$\psi=\psi_{1}\vee\psi_{2}$: there is exactly one $\tau\in\mathsf{choices}$
such that $L(q,\tau)\neq\emptyset$. Put $s(q,\psi)=(q,\tau(\psi))$, having
$q\in\widehat{[\\![\tau(\psi)]\\!]}$.

  3. (3)

$\psi=\eta X.\,\psi_{1}$: Put $s(q,\psi)=(q,\psi_{i}[\psi/X])$ (the only
available move), having $q\in\widehat{[\\![\psi_{i}[\psi/X]]\\!]}$.

  4. (4)

$\psi=\heartsuit\psi_{1}$: Then $q\in\widehat{[\\![\heartsuit\psi_{1}]\\!]}$;
since $\xi$ is coherent, we thus have
$\xi(q)\in[\\![\heartsuit]\\!](\widehat{[\\![\psi]\\!]}\cap
L(q,\mathsf{selections}))$, so we can put
$s(q,\psi)=(\widehat{[\\![\psi_{1}]\\!]}\cap
L(q,\mathsf{selections}),\heartsuit\psi_{1})$.

We have to show that $s$ is a winning strategy; since, as we have noted, the
game never reaches a node of the form $(q,\bot)$, it is clear that $\exists$
wins all finite plays, so it remains only to consider infinite plays $\pi$,
compatible with $s$. Roughly speaking, $\pi$ induces, in a way explained
below, a (not necessarily unique) path
$\bar{\pi}=(q_{\mathsf{init}},\sigma_{0}),(q_{1},\sigma_{1}),\ldots$ in the
tableau $(W,L)$ and a sequence $\rho=\psi_{0},\psi_{1},\ldots$ of formulae
$\psi_{i}\in\mathbf{F}$ such that $\psi_{0}=\chi$ and
$\psi_{i+1}\in\Delta(\psi_{i},\sigma_{i})$ for $i\geq 0$. Thus, the sequence
$\rho$ is a run of $\mathsf{A}_{\chi}$ on the word
$w=\sigma_{0},\sigma_{1},\ldots$. As $(W,L)$ is a tableau, $w$ is accepted by
$\mathsf{B}_{\chi}$, so $\rho$ is a non-accepting run of $\mathsf{A}_{\chi}$.
As the winning objective in $\mathsf{G}_{{\chi,(V,\xi)}}$ is dual to
acceptance in $\mathsf{A}_{\chi}$, the existential player thus wins the play
$\pi$.

It remains to explain in detail how $\pi$ induces $\bar{\pi}$ and $\rho$ as
above inductively. We look at steps of $\pi$ starting in a node of the form
$(q,\psi)$, distinguishing cases over the shape of $\psi$, where $\psi=\top$
and $\psi=\bot$ do not occur because $\pi$ is infinite. For $\psi$ of the form
$\psi_{1}\vee\psi_{2}$, $\psi_{1}\land\psi_{2}$, or $\eta X.\,\psi_{1}$, the
node $q$ remains the same, the next letter is the unique
$\tau\in\mathsf{choices}$ such that $L(q,\tau)\neq\emptyset$, and the next
formula $\psi^{\prime}$ is determined either by $s$ as defined above or, in
case $\psi=\psi_{1}\land\psi_{2}$, by a move of $\forall$; in either case,
$\psi^{\prime}\in\Delta(\psi,\tau)$ according to the rules of
$\mathsf{G}_{\chi,(V,\xi)}$. Finally, if $\psi=\heartsuit\psi_{1}$, then
$s(q,\psi)=(D,\heartsuit\psi_{1})$ where $D=\widehat{[\\![\psi_{1}]\\!]}\cap
L(q,\mathsf{selections})$, and the subsequent move of $\forall$ ends up in a
node $(q^{\prime},\psi_{1})$ where $q^{\prime}\in D$, so there exists
$\kappa\in\mathsf{selections}$ such that $\psi_{1}\in\Delta(q,\kappa)$. We can
thus continue $\bar{\pi}$ with $(q^{\prime},\kappa)$, and $\rho$ with
$\psi_{1}$.

It remains to prove soundness.

######  Lemma 44 (Soundness).

Let $\chi$ be satisfiable. Then the existential player wins
$\mathsf{G}_{\chi}$.

######  Proof 5.4.

Fix a coalgebra $(C,\xi)$ and a state $x_{0}\in C$ such that
$x_{0}\models\chi$. We construct a _history-dependent_ strategy $s\colon
V^{*}V_{\exists}\rightharpoonup V_{\forall}$ for the existential player in the
satisfiability game $\mathsf{G}_{\chi}$. During the construction, we maintain
the invariant that for any partial play $v_{0},v_{1},\ldots,(q,b)\in
V^{*}V_{\exists}$ ending in the node $(q,b)\in
V_{\exists}=D_{\chi}\times\\{0,1\\}$, there is $x\in C$ such that

$\text{for all }\psi\in l^{A}(q),\text{ the existential player wins
}(x,\psi)\text{ in }\mathsf{G}_{{\chi,(C,\xi)}};$

we call such an $x$ a _realizer_ of $q$. More precisely, we keep the realizer
in memory, and in each step, we construct the new realizer from the previous
one; this is why the strategy we construct is not history-free. We write
$s((q,b),x)$ for the move recommended by $s$ when in a position $(q,b)\in
V_{\exists}$ with realizer $x$.

We can pick $x_{0}$ as the realizer of $q_{\mathsf{init}}$, ensuring that the
invariant holds initially: We have $l^{A}(q_{\mathsf{init}})=\\{\chi\\}$ and
$x_{0}\models\chi$, so the existential player wins $(x_{0},\chi)$ in the model
checking game $\mathsf{G}_{{\chi,(C,\xi)}}$ by Lemma 21. We fix a strategy
$s^{\prime}$ for the existential player in $\mathsf{G}_{\chi,(C,\xi)}$ with
which she wins every node in her winning region. To see that the existential
player can maintain the invariant, let $(q,b)\in
V_{\exists}=D_{\chi}\times\\{0,1\\}$ and let $x\in C$ be a realizer of $q$. We
distinguish cases over $b$.

$b=0$: We put $s((q,0),x)=\delta(q,\tau)$, where $\tau\in\mathsf{choices}$ is
obtained as follows. For each formula $\psi\in l^{A}(q)$, the existential
player wins $(x,\psi)$ in $\mathsf{G}_{{\chi,(C,\xi)}}$ by the invariant. For
each disjunction $\psi=\psi_{1}\vee\psi_{2}\in l^{A}(q)$, we have
$s^{\prime}(x,\psi)=(x,\psi_{i})$ for some $i\in\\{1,2\\}$; we put
$\tau(\psi)=\psi_{i}$. The existential player wins the node $(x,\psi_{i})$ in
$\mathsf{G}_{{\chi,(C,\xi)}}$ since $s^{\prime}$ is a winning strategy. For
disjunctions $\psi\in\mathbf{F}$ not contained in $l^{A}(q)$, define
$\tau(\psi)$ arbitrarily.

From $\delta(q,\tau)$, the satisfiability game reaches a node of the form
$(\delta(q,\tau),b^{\prime})$ after the next move of $\forall$. To establish
the invariant, we pick the original realizer $x$ of $q$ as the new realizer of
$\delta(q,\tau)$. We have to show that for all $\psi\in
l^{A}(\delta(q,\tau))$, the existential player wins $(x,\psi)$ in in
$\mathsf{G}_{{\chi,(C,\xi)}}$. By the definition of the tracking automaton
(Definition 11), such a $\psi$ arises in one of the following ways:

  * •

$\psi$ is a disjunct of disjunction in $l^{A}(q)$. It was shown above that the
existential player wins $(x,\psi)$ in this case.

  * •

$\psi$ is a conjunct (w.l.o.g., the left one) of a formula $\psi\land\phi\in
l^{A}(q)$. Then the universal player can move from $(x,\psi\land\phi)$ to
$(x,\psi)$ in $\mathsf{G}_{{\chi,(C,\xi)}}$. Since the existential player wins
$(x,\psi\land\phi)$ by the invariant, she thus also wins $(x,\psi)$.

  * •

If $\psi=\psi_{1}[\eta X.\,\psi_{1}/X]$ for some $\eta X.\,\psi_{1}\in
l^{A}(q)$, then the existential player wins $(x,\eta X.\,\psi_{1})$ in
$\mathsf{G}_{{\chi,(C,\xi)}}$ by the invariant, and her only move from this
node is to $(x,\psi)$, so she also wins the latter node.

Having established the invariant that there is a state $x\in C$ such that for
all $\psi\in l^{A}(\delta(q,\tau))$, the existential player wins $(x,\psi)$ in
$\mathsf{G}_{{\chi,(C,\xi)}}$, we note that the invariant for $(q,0)$ also
implies $\bot\notin l^{A}(q))$, so $((q,0),\delta(q,\tau))$ is in fact a valid
move in $\mathsf{G}_{\chi}$.

$b=1$: For each $\heartsuit\psi\in l^{A}(q)$, the existential player wins
$(x,\heartsuit\psi)$ in $\mathsf{G}_{{\chi,(C,\xi)}}$ by the invariant. Then
$s^{\prime}(x,\heartsuit\psi)$ has the form

$s^{\prime}(x,\heartsuit\psi)=(A_{\heartsuit\psi},\heartsuit\psi)\quad\text{where}\quad\xi(x)\in[\\![\heartsuit]\\!](A_{\heartsuit\psi}).$
(7)

Put
$\Xi=\\{\kappa\in\mathsf{selections}\mid\bigcap_{\heartsuit\psi\in\kappa}A_{\heartsuit\psi}\neq\emptyset\\}$.
For $\kappa\in\Xi$, fix an element
$y_{\kappa}\in\bigcap_{\heartsuit\psi\in\kappa}A_{\heartsuit\psi}$. We put
$s((q,1),x)=(q,\Xi)$. The ensuing moves of the universal player then reach a
node in $V_{\exists}$ of the form $(\delta(q,\kappa),b^{\prime})$ where
$\kappa\in\Xi$. We pick $y_{\kappa}$ as the realizer of $\delta(q,\kappa)$. To
show that this ensures the invariant, let $\psi\in l^{A}(\delta(q,\kappa))$,
that is, $\heartsuit\psi\in\kappa$ for some $\heartsuit\in\Lambda$; we have to
show that the existential player wins $(y_{\kappa},\psi)$. But this follows
from the fact that $s^{\prime}$ is a winning strategy and the universal player
can move from
$s^{\prime}(x,\heartsuit\psi)=(A_{\heartsuit\psi},\heartsuit\psi)$ to
$(y_{\kappa},\psi)$, since $y_{\kappa}\in A_{\heartsuit\psi}$.

It remains to show that $((q,1),(q,\Xi))$ is a valid move in
$\mathsf{G}_{\chi}$, that is, that we have

$[\\![l^{A}(q)\cap\Lambda(\mathbf{F})]\\!]^{H}_{1}\neq\emptyset,$ (8)

where $H=\\{l^{A}(\delta(q,\kappa))\mid\kappa\in\Xi\\}$. We prove this using
Lemma 27 (and notation introduced therein). We put
$V=\\{a_{\heartsuit\psi}\mid\heartsuit\psi\in\mathbf{F})\\}$, and we define a
labelling $l^{x}\colon C\to\mathcal{P}(V)$ by

$l^{x}(y)=\\{a_{\heartsuit\psi}\in V\mid y\in A_{\heartsuit\psi}\\}.$ (9)

We define a map

$g\colon V\to\mathbf{F},a_{\heartsuit\psi}\mapsto\psi.$

(Note in particular that $a_{\heartsuit\psi}\in V$ is used as a placeholder
for $\psi$ and not for $\heartsuit\psi$; the modality $\heartsuit$ is needed
in the index to enable the definition (9) of $l^{x}$ because for each
$\heartsuit$, $\exists$ may claim a different set $A_{\heartsuit\psi}$ to be
contained in the extension of $\psi$.) We check that this map satisfies the
assumptions of Lemma 27, applied to $l^{x}[C]$ and $H$. So let $y\in C$; we
have to find $\kappa\in\Xi$ such that $g[l^{x}(y)]\subseteq
l^{A}(\delta(q,\kappa))$. Indeed, this inclusion holds for
$\kappa:=\\{\heartsuit\psi\mid a_{\heartsuit\psi}\in l^{x}(y)\\}$: Given
$a_{\heartsuit\psi}\in l^{x}(y)$, that is, $y\in A_{\heartsuit\psi}$, we have
$g(a_{\heartsuit\psi})=\psi\in\\{\rho\mid\heartsuit\rho\in\kappa\\}\overset{\eqref{eq:det-
label-modal}}{=}l^{A}(\delta(q,\kappa))$. It remains to show that
$\kappa\in\Xi$. By the relevant definitions, this amounts to showing that
$A:=\bigcap_{a_{\heartsuit\psi}\in l^{x}(y)}A_{\heartsuit\psi}\neq\emptyset$;
but $y\in A$ by definition of $l^{x}(y)$. Now put $\gamma=\\{\heartsuit
a_{\heartsuit\psi}\mid\heartsuit\psi\in\mathbf{F}\cap l^{A}(q)\\}$. Then
$\gamma_{g}=l^{A}(q)\cap\Lambda(\mathbf{F})$, so (8) follows by Lemma 27 once
we show that

$[\\![\gamma]\\!]^{l^{x}[C]}_{1}\neq\emptyset.$

We claim that $Fl^{x}(\xi(x))\in[\\![\gamma]\\!]^{l^{x}[C]}_{1}$. So let
$\heartsuit a_{\heartsuit\psi}\in\gamma$, that is,
$\heartsuit\psi\in\mathbf{F}\cap l^{A}(q)$; we have to show
$Fl^{x}(\xi(x))\in[\\![\heartsuit]\\!]_{l^{x}[C]}[\\![a_{\heartsuit\psi}]\\!]^{l^{x}[C]}_{0}$,
which by naturality is equivalent to
$\xi(x)\in[\\![\heartsuit]\\!]_{C}((l^{x})^{-1}[[\\![a_{\heartsuit\psi}]\\!]^{l^{x}[C]}_{0}])=[\\![\heartsuit]\\!]_{C}(A_{\heartsuit\psi})$;
but this holds by (7).

This concludes the proof that $s$ is a strategy, that is, yields legal moves
in $\mathsf{G}_{\chi}$. It remains to show that $s$ is winning. So let $\pi$
be a play that starts at $v_{0}$ and follows $s$. Then $\pi$ gives rise to a
finite or infinite word $w=\sigma_{0},\sigma_{1},\ldots$ over $\Sigma$: The
play $\pi$ consists of concatened subplays $\pi_{i}$ that are of the shape
$q_{i},(q_{i},0),q_{i+1}$ where $q_{i+1}=\delta(q_{i},\sigma_{i})$ for some
$\sigma_{i}\in\mathsf{choices}$, or of the shape
$q_{i},(q_{i},1),(q_{i},\Xi),q_{i+1}$ where $q_{i+1}=\delta(q_{i},\sigma_{i})$
for some $\sigma_{i}\in\Xi$. In particular, the sequence
$q_{\mathsf{init}},q_{1},\ldots$ is the run of $\mathsf{B}_{\chi}$ on the word
$w$. We have to show that the existential player wins $\pi$. If $\pi$ is a
finite play, then it ends in a node $(q,\emptyset)\in V_{\forall}$ so that the
existential player wins $\pi$. If $\pi$ is infinite, then we note that the
winning objective of the existential player in $\mathsf{G}_{\chi}$ is $w\in
L(\mathsf{B}_{\chi})$. Since $w\in
L(\mathsf{B}_{\chi})=\overline{L(\mathsf{A}_{\chi})}$, we show equivalently
that every run $\rho$ of $\mathsf{A}_{\chi}$ on the word $w$ is non-accepting.
We recall that the strategy $s$ is built, via the notion of realizer, along a
winning strategy $s^{\prime}$ in the model checking game so that $\rho$
induces a play of the model checking game that starts at $(x_{0},\chi)$ and
follows $s^{\prime}$, hence is won by the existential player. As the objective
in the model checking game is dual to the priority function in
$\mathsf{A}_{\chi}$, $\rho$ is a non-accepting run of $\mathsf{A}_{\chi}$.

We are now essentially done; the results so far are tied up as follows,
establishing soundness and completeness of our global caching algorithm
(Algorithm 1):

######  Corollary 45 (Soundness and completeness).

The following are equivalent:

  1. (1)

We have $q_{\mathsf{init}}\in\mathbf{E}$.

  2. (2)

The existential player wins the node $q_{\mathsf{init}}$ in
$\mathsf{G}_{\chi}$.

  3. (3)

There is a tableau for $\chi$.

  4. (4)

The formula $\chi$ is satisfiable.

######  Proof 5.5.

The equivalence of (1) and (2) is Lemma 31, and the implication
(2)$\implies$(3) is Lemma 38. We have shown the implication (4)$\implies$(2)
in Lemma 44. We prove (3)$\implies$(4): Let $(W,L)$ be a tableau for $\chi$.
By the existence lemma (Lemma 42), there is a coherent coalgebra built over
$(W,L)$, which by the truth lemma (Lemma 43) is a model for $\chi$.

Our model construction in the proof of Lemma 42 moreover yields the same bound
on minimum model size as in earlier work on the coalgebraic $\mu$-calculus
[CKP11a]:

######  Corollary 46 (Small-model property).

Let $\chi$ be a satisfiable coalgebraic $\mu$-calculus formula. Then $\chi$
has a model of size $\mathcal{O}(((nk)!)^{2})\in 2^{\mathcal{O}(nk\log n)}$.

######  Remark 47 (Polynomially branching models).

In addition to having an exponentially bounded number of states (Corollary
46), the models $(V,\xi)$ constructed in the above completeness proof are also
polynomially branching, provided that the logic has the one-step polysize
model property, which holds in all our running examples (Remark 26). By this
we mean that there is a polynomial $p$ such that for every $q\in V$, there is
a subset $V_{0}\subseteq V$ such that $|V_{0}|\leq p(n)$ and $\xi(q)$ has the
form $\xi(q)=Fi(t)$ where $i\colon V_{0}\to V$ is the subset inclusion. This
property is immediate from the construction of coherent coalgebras in the
proof of the existence lemma (Lemma 42), in which $\xi(q)$ is obtained from a
model of a one-step pair over $\mathbf{F}$. With the exception of the standard
$\mu$-calculus, this bound appears to be new in all our example logics. Of
course, for graded and Presburger $\mu$-calculi, polynomial branching holds
only in their coalgebraic semantics, i.e. over multigraph models but not over
Kripke models.

##  6\. Conclusion

We have shown that the satisfiability problem of the coalgebraic
$\mu$-calculus is in ExpTime, subject to establishing a suitable time bound on
the much simpler one-step satisfiability problem. Prominent examples include
the graded $\mu$-calculus, the (two-valued) probabilistic $\mu$-calculus, and
extensions of the probabilistic and the graded $\mu$-calculus, respectively,
with (monotone) polynomial inequalities; the ExpTime bound appears to be new
for the last two logics. We have also presented a generic satisfiability
algorithm that realizes the time bound and supports global caching and on-the-
fly solving. Moreover, we have obtained a polynomial bound on minimum
branching width in models for all example logics mentioned above.

## References

  * [AHK02] Rajeev Alur, Thomas Henzinger, and Orna Kupferman.  Alternating-time temporal logic.  J. ACM, 49:672–713, 2002.
  * [AHS90] Jiří Adámek, Horst Herrlich, and George Strecker.  Abstract and concrete categories.  Wiley, 1990.  Also: Reprints in Theory and Applications of Categories 17 (2006), 1–507.
  * [AM89] Peter Aczel and Nax Mendler.  A final coalgebra theorem.  In Proc. Category Theory and Computer Science (CTCS), volume 389 of LNCS, pages 357–365. Springer, 1989.
  * [BFL15] Florian Bruse, Oliver Friedmann, and Martin Lange.  On guarded transformation in the modal $\mu$-calculus.  Log. J. IGPL, 23(2):194–216, 2015.
  * [BKMP19] Paolo Baldan, Barbara König, Christina Mika-Michalski, and Tommaso Padoan.  Fixpoint games on continuous lattices.  Proc. ACM Program. Lang., 3(POPL):26:1–26:29, 2019.
  * [BS06] Julian Bradfield and Colin Stirling.  Modal $\mu$-calculi.  In Patrick Blackburn, Johan van Benthem, and Frank Wolter, editors, Handbook of Modal Logic, pages 721–756. Elsevier, 2006.
  * [BSdV04] Falk Bartels, Ana Sokolova, and Erik de Vink.  A hierarchy of probabilistic system types.  Theor. Comput. Sci., 327:3–22, 2004.
  * [BW18] Julian Bradfield and Igor Walukiewicz.  The mu-calculus and model checking.  In Edmund Clarke, Thomas Henzinger, Helmut Veith, and Roderick Bloem, editors, Handbook of Model Checking, pages 871–919. Springer, 2018.
  * [Can88] John Canny.  Some algebraic and geometric computations in PSPACE.  In Symposium on Theory of Computing, STOC 1988, pages 460–467. ACM, 1988.
  * [CC79] Patrick Cousot and Radhia Cousot.  Constructive versions of Tarski’s fixed point theorems.  Pacific J. Math., 81(1):43–57, 1979.
  * [CIN05] Rance Cleaveland, S. Iyer, and Murali Narasimha.  Probabilistic temporal logics via the modal $\mu$-calculus.  Theor. Comput. Sci., 342:316–350, 2005.
  * [CKP11a] Corina Cîrstea, Clemens Kupke, and Dirk Pattinson.  EXPTIME tableaux for the coalgebraic $\mu$-calculus.  Log. Meth. Comput. Sci., 7, 2011.
  * [CKP+11b] Corina Cîrstea, Alexander Kurz, Dirk Pattinson, Lutz Schröder, and Yde Venema.  Modal logics are coalgebraic.  Comput. J., 54:31–41, 2011.
  * [CKW18] Sjoerd Cranen, Jeroen J. A. Keiren, and Tim A. C. Willemse.  Parity game reductions.  Acta Informatica, 55(5):401–444, 2018.
  * [DL06] Stéphane Demri and Denis Lugiez.  Presburger modal logic is PSPACE-complete.  In Ulrich Furbach and Natarajan Shankar, editors, Automated Reasoning, IJCAR 2006, volume 4130 of LNCS, pages 541–556. Springer, 2006.
  * [DV02] Giovanna D’Agostino and Albert Visser.  Finality regained: A coalgebraic study of Scott-sets and multisets.  Arch. Math. Logic, 41:267–298, 2002.
  * [EJ91] E.A. Emerson and C.S. Jutla.  Tree automata, mu-calculus and determinacy.  In [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 368–377, 1991.
  * [EJ99] E. Allen Emerson and Charanjit Jutla.  The complexity of tree automata and logics of programs.  SIAM J. Comput., 29(1):132–158, September 1999.
  * [EKRS17] Javier Esparza, Jan Kretínský, Jean-François Raskin, and Salomon Sickert.  From LTL and limit-deterministic büchi automata to deterministic parity automata.  In Axel Legay and Tiziana Margaria, editors, Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2017, volume 10205 of LNCS, pages 426–442. Springer, 2017.
  * [ES06] Friedrich Eisenbrand and Gennady Shmonin.  Carathéodory bounds for integer cones.  Oper. Res. Lett., 34(5):564–568, 2006.
  * [FHM90] Ronald Fagin, Joseph Halpern, and Nimrod Megiddo.  A logic for reasoning about probabilities.  Inform. Comput., 87:78–128, 1990.
  * [FL13] Oliver Friedmann and Martin Lange.  Deciding the unguarded modal $\mathrm{\mu}$-calculus.  J. Appl. Non-Classical Log., 23:353–371, 2013.
  * [FLL13] Oliver Friedmann, Markus Latte, and Martin Lange.  Satisfiability games for branching-time logics.  Log. Methods Comput. Sci., 9, 2013.
  * [FLV10] Gaëlle Fontaine, Raul Andres Leal, and Yde Venema.  Automata for coalgebras: An approach using predicate liftings.  In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul Spirakis, editors, Automata, Languages and Programming, ICALP 2010, volume 6199 of LNCS, pages 381–392. Springer, 2010.
  * [GJLS17] Víctor Gutiérrez-Basulto, Jean Christoph Jung, Carsten Lutz, and Lutz Schröder.  Probabilistic description logics for subjective uncertainty.  J. Artif. Intell. Res., 58:1–66, 2017.
  * [GN13] Rajeev Goré and Linh Anh Nguyen.  Exptime tableaux for _ALC_ using sound global caching.  J. Autom. Reasoning, 50:355–381, 2013.
  * [GTW02] Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors.  Automata Logics, and Infinite Games: A Guide to Current Research.  Springer, 2002.
  * [GW09] Rajeev Goré and Florian Widmann.  Sound global state caching for $\mathcal{ALC}$ with inverse roles.  In Martin Giese and Arild Waaler, editors, Automated Reasoning with Analytic Tableaux and Related Methods, TABLEAUX 2009, volume 5607 of LNCS, pages 205–219. Springer, 2009.
  * [HK97] Michael Huth and Marta Kwiatkowska.  Quantitative analysis and model checking.  In Logic in Computer Science, LICS 1997, pages 111–122. IEEE, 1997\.
  * [HP06] Thomas A. Henzinger and Nir Piterman.  Solving games without determinization.  In Zoltán Ésik, editor, Computer Science Logic, CSL 2006, volume 4207 of LNCS, pages 395–410. Springer, 2006.
  * [HS15] Daniel Hausmann and Lutz Schröder.  Global caching for the flat coalgebraic $\mu$-calculus.  In Fabio Grandi, Martin Lange, and Alessio Lomuscio, editors, Temporal Representation and Reasoning, TIME 2015, pages 121–143. IEEE, 2015\.
  * [HS19] Daniel Hausmann and Lutz Schröder.  Optimal satisfiability checking for arithmetic $\mu$-calculi.  In Mikolaj Bojanczyk and Alex Simpson, editors, Foundations of Software Science and Computation Structures, FOSSACS 2019, volume 11425 of LNCS, pages 277–294. Springer, 2019.
  * [HS21] Daniel Hausmann and Lutz Schröder.  Quasipolynomial computation of nested fixpoints.  In Jan Friso Groote and Kim Guldstrand Larsen, editors, Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2021, volume 12651 of LNCS, pages 38–56. Springer, 2021.
  * [HSD18] Daniel Hausmann, Lutz Schröder, and Hans-Peter Deifel.  Permutation games for the weakly aconjunctive $\mu$-calculus.  In Dirk Beyer and Marieke Huisman, editors, Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2018, volume 10806 of LNCS, pages 361–378. Springer, 2018.
  * [HSE16] Daniel Hausmann, Lutz Schröder, and Christoph Egger.  Global caching for the alternation-free coalgebraic $\mu$-calculus.  In Josée Desharnais and Radha Jagadeesan, editors, Concurrency Theory, CONCUR 2016, volume 59 of LIPIcs, pages 34:1–34:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [KKV01] Valerie King, Orna Kupferman, and Moshe Vardi.  On the complexity of parity word automata.  In Furio Honsell and Marino Miculan, editors, Foundations of Software Science and Computation Structures, FOSSACS 2001, volume 2030 of LNCS, pages 276–286. Springer, 2001.
  * [KMV20] Clemens Kupke, Johannes Marti, and Yde Venema.  Size matters in the modal $\mu$-calculus.  CoRR, abs/2010.14430, 2020.
  * [Koz83] Dexter Kozen.  Results on the propositional $\mu$-calculus.  Theor. Comput. Sci., 27:333–354, 1983.
  * [KP10] Clemens Kupke and Dirk Pattinson.  On modal logics of linear inequalities.  In Lev Beklemishev, Valentin Goranko, and Valentin Shehtman, editors, Advances in Modal Logic, AiML 2010, pages 235–255. College Publications, 2010.
  * [KPS15] Clemens Kupke, Dirk Pattinson, and Lutz Schröder.  Reasoning with global assumptions in arithmetic modal logics.  In Adrian Kosowski and Igor Walukiewicz, editors, Fundamentals of Computation Theory, FCT 2015, volume 9210 of LNCS, pages 367–380. Springer, 2015.
  * [KPS22] Clemens Kupke, Dirk Pattinson, and Lutz Schröder.  Coalgebraic reasoning with global assumptions in arithmetic modal logics.  ACM Trans. Comput. Log., 23(2):11:1–11:34, 2022.
  * [KSV02] Orna Kupferman, Ulrike Sattler, and Moshe Vardi.  The complexity of the graded $\mu$-calculus.  In Andrei Voronkov, editor, Automated Deduction, CADE 02, volume 2392 of LNCS, pages 423–437. Springer, 2002.
  * [KV08] Clemens Kupke and Yde Venema.  Coalgebraic automata theory: Basic results.  Log. Methods Comput. Sci., 4(4), 2008.
  * [Lav76] R. Laver.  Well-quasi-orders and sets of finite sequences.  Math. Proc. Cambridge Philos. Soc., 79:1–10, 1976.
  * [LBC+94] David E. Long, Anca Browne, Edmund M. Clarke, Somesh Jha, and Wilfredo R. Marrero.  An improved algorithm for the evaluation of fixpoint expressions.  In Computer Aided Verification, CAV 1994, volume 818 of LNCS, pages 338–350. Springer, 1994.
  * [LSWZ15] Wanwei Liu, Lei Song, Ji Wang, and Lijun Zhang.  A simple probabilistic extension of modal mu-calculus.  In Qiang Yang and Michael Wooldridge, editors, International Joint Conference on Artificial Intelligence, IJCAI 2015, pages 882–888. AAAI Press, 2015.
  * [Mar75] Donald A. Martin.  Borel determinacy.  Annals of Mathematics, 102(2):363–371, 1975.
  * [MH84] Satoru Miyano and Takeshi Hayashi.  Alternating finite automata on $\omega$-words.  Theor. Comput. Sci., 32:321–330, 1984.
  * [Mio11] Matteo Mio.  Probabilistic modal $\mu$-calculus with independent product.  In Martin Hofmann, editor, Foundations of Software Science and Computational Structures, FOSSACS 2011, volume 6604 of LNCS, pages 290–304. Springer, 2011.
  * [MM07] Annabelle McIver and Carroll Morgan.  Results on the quantitative $\mathrm{\mu}$-calculus qm$\mathrm{\mu}$.  ACM Trans. Comput. Log., 8, 2007.
  * [Mos99] Lawrence Moss.  Coalgebraic logic.  Ann. Pure Appl. Log., 96(1-3):277–317, 1999.
  * [MPS09] Robert Myers, Dirk Pattinson, and Lutz Schröder.  Coalgebraic hybrid logic.  In Luca de Alfaro, editor, Foundations of Software Science and Computational Structures, FOSSACS 2009, volume 5504 of LNCS, pages 137–151. Springer, 2009.
  * [Par85] Rohit Parikh.  The logic of games and its applications.  Ann. Discr. Math., 24:111–140, 1985.
  * [Pat03] Dirk Pattinson.  Coalgebraic modal logic: Soundness, completeness and decidability of local consequence.  Theor. Comput. Sci., 309:177–193, 2003.
  * [Pat04] Dirk Pattinson.  Expressive logics for coalgebras via terminal sequence induction.  Notre Dame J. Formal Logic, 45:19–33, 2004.
  * [Pit07] Nir Piterman.  From nondeterministic Büchi and Streett automata to deterministic parity automata.  Log. Meth. Comput. Sci., 3, 2007.
  * [PS10] Dirk Pattinson and Lutz Schröder.  Cut elimination in coalgebraic logics.  Inf. Comput., 208(12):1447–1468, 2010.
  * [RdV99] Jan Rutten and Erik de Vink.  Bisimulation for probabilistic transition systems: a coalgebraic approach.  Theor. Comput. Sci., 221:271–293, 1999.
  * [Rut00] Jan Rutten.  Universal coalgebra: A theory of systems.  Theor. Comput. Sci., 249:3–80, 2000.
  * [Saf88] Shmuel Safra.  On the complexity of omega-automata.  In Foundations of Computer Science, FOCS 1988, pages 319–327. IEEE Computer Society, 1988.
  * [Sch86] Alexander Schrijver.  Theory of linear and integer programming.  Wiley Interscience, 1986.
  * [Sch07] Lutz Schröder.  A finite model construction for coalgebraic modal logic.  J. Log. Algebr. Prog., 73:97–110, 2007.
  * [Sch08] Lutz Schröder.  Expressivity of coalgebraic modal logic: The limits and beyond.  Theor. Comput. Sci., 390(2-3):230–247, 2008.
  * [Sei96] Helmut Seidl.  Fast and Simple Nested Fixpoints.  Inf. Process. Lett., 59:303–308, 1996.
  * [SP08] Lutz Schröder and Dirk Pattinson.  Shallow models for non-iterative modal logics.  In Andreas Dengel, Karsten Berns, Thomas Breuel, Frank Bomarius, and Thomas Roth-Berghofer, editors, Advances in Artificial Intelligence, KI 2008, volume 5243 of LNCS, pages 324–331. Springer, 2008.
  * [SP09] Lutz Schröder and Dirk Pattinson.  PSPACE bounds for rank-1 modal logics.  ACM Trans. Comput. Log., 10(2):13:1–13:33, 2009.
  * [SP11] Lutz Schröder and Dirk Pattinson.  Modular algorithms for heterogeneous modal logics via multi-sorted coalgebra.  Math. Struct. Comput. Sci., 21:235–266, 2011.
  * [SV18] Lutz Schröder and Yde Venema.  Completeness of flat coalgebraic fixpoint logics.  ACM Trans. Comput. Log., 19(1):4:1–4:34, 2018.
  * [Ven06] Yde Venema.  Automata and fixed point logic: A coalgebraic perspective.  Inf. Comput., 204(4):637–678, 2006.
  * [Wil01] Thomas Wilke.  Alternating tree automata, parity games, and modal $\mu$-calculus.  Bull. Belg. Math. Soc., 8(2):359–391, 2001.