$\begingroup$
$\endgroup$
5
A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik Grundlagen Math. 6 (1960) 66-92).
- Are there proofs of non-regularity of a language $L$ (e.g. $L = \{ a^n b^n \}$) that are based on the non expressibility in MSO of $L$?
- What are the (logic) techniques (if any) that can be used?
I googled a little bit, but didn't find anything relevant (but I'm not an expert, so I'm probably using the wrong terms).
Raphael
73.4k31 gold badges184 silver badges406 bronze badges
-
4$\begingroup$ Everything I've found (in a non-exhaustive search) goes the other way - using non-regularity to show inexpressibility in MSO. Even Ebbinghaus & Flum's "Finite Model Theory" only has examples in that direction (if you have it handy, Chapter 7, pp. 112-113, 2nd Ed.). $\endgroup$Luke Mathieson– Luke Mathieson2016年01月19日 00:33:53 +00:00Commented Jan 19, 2016 at 0:33
-
4$\begingroup$ I agree with @luke-mathieson . All examples I know go the other way. If that helps, note that, over strings, MSO = $\exists$MSO. Thus it would suffice to prove non expressibility in $\exists$MSO. $\endgroup$J.-E. Pin– J.-E. Pin2016年01月19日 18:38:45 +00:00Commented Jan 19, 2016 at 18:38
-
$\begingroup$ The usual way to directly show something is not expressible in descriptive complexity/finite model theory is to use some variation of Ehrenfeucht-Fraisse games. $\endgroup$Kaveh– Kaveh2016年02月08日 12:57:23 +00:00Commented Feb 8, 2016 at 12:57
-
$\begingroup$ But in a way also Büchi was working the other way. Not per sé interested in the regualr languages, but in applying their decidability to MSO logic? $\endgroup$Hendrik Jan– Hendrik Jan2016年03月18日 16:54:29 +00:00Commented Mar 18, 2016 at 16:54
-
1$\begingroup$ This essay defines EF games for MSO definable formulas. While it shows only that the class of finite structures is not MSO-definable (which doesn't correspond to a non-regular language), perhaps an argument can be made to show that $\{ 0^n 1^n \mid n \in \mathbb{N}\}$ is not MSO-definable, just by showing the duplicator wins the $n$-turn game on strings 0ドル^n 1^n$ and 0ドル^{n+1} 1^{n+1}$. $\endgroup$Caleb Stanford– Caleb Stanford2017年04月12日 09:02:59 +00:00Commented Apr 12, 2017 at 9:02