It is known that WS1S can be decided by a DFA. Is this the strongest arithmetic theory decidable by a DFA? What happens when the automata class is extended to include DPDAs or PDAs?

  • $\begingroup$ Question: how is going from a DFA to a PDA weakening? Aren’t PDAs capable of recognizing more languages, and therefore stronger? $\endgroup$ – D. Ben Knoble Jan 26 '20 at 17:14
  • $\begingroup$ @D.BenKnoble I was thinking of "weaker" in a different sense. Question edited. $\endgroup$ – danportin Jan 26 '20 at 19:30
  • $\begingroup$ The slides you link to do not provide a proof of regularity, and I find the claim that S1S can be decided by DFAs weird. How do you represent infinite sets? This is commonly done with $\omega$-automata. $\endgroup$ – Shaull Jan 26 '20 at 19:38
  • 1
    $\begingroup$ @Shaull Right, it's WS1S that's regular. $\endgroup$ – danportin Jan 26 '20 at 19:49

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.