19
$\begingroup$

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).

  1. 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$?
  2. 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
asked Jan 18, 2016 at 23:29
$\endgroup$
5
  • 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$ Commented 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$ Commented 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$ Commented 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$ Commented 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$ Commented Apr 12, 2017 at 9:02

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.