0
$\begingroup$

What is the Monodic Second Order formula that encodes all binary strings that represent a valid parenthesis matching ? By this I mean 1s represent '(' and 0s represent ')' and at every position, number of 1s in the prefix is greater than or equal to the number of 0s .

Can someone tell me how to proceed ?

Thanks!

$\endgroup$
4
  • $\begingroup$ Can you possibly formalize the question more rigorously, I'm not exactly sure what you are asking for. $\endgroup$ Apr 6 '17 at 6:32
  • $\begingroup$ Sorry for the confusion. The words in the language are formed using 0s and 1s . At every position, number of 1s in the prefix is greater than or equal to the number of 0s . For Example, 1100 is a valid word but 1001 is not. $\endgroup$
    – Xin Yin
    Apr 6 '17 at 9:49
  • $\begingroup$ I also want to capture the fact that the total number of ones and zeros in the word are the same $\endgroup$
    – Xin Yin
    Apr 6 '17 at 9:51
  • 1
    $\begingroup$ Standard MSO logic on strings define the regular languages, so you have to explain what predicates you are allowed to use? $\endgroup$ Apr 6 '17 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.