# Tag Info

22

I also have the impression that Descriptive Complexity is a less active area of research nowadays. Nevertheless, there are some topics in which people are still active: Rank logics: Rank Logic is Dead, Long Live Rank Logic! by Grädel and Pakusa Symmetric Circuits for Rank Logic by Dawar and Wilsenach Separating Rank Logic from Polynomial Time by Lichter ...

11

Definitely still active in the area of Weisfeiler-Leman-style algorithms for isomorphism problems such as Graph Isomorphism. The connection with logic was first (I believe) made in Immerman-Lander and Cai-Fürer-Immerman. Very recently adapted to Group Isomorphism [Brachter-Schweitzer]. Certain logics are equivalent in their power to distinguish graphs (resp....

2

Lemma 1. Consider $L = (ab)^* + (ba)^*$: There exists CFG with two variables which generates $L$ There exist no CFG with one variable which generates $L$ For proving (1) we may just consider the following CFG $$S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$ The second proposition is a bit more tricky. Suppose that there exists CFG \$G = ...

Only top voted, non community-wiki answers of a minimum length are eligible