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$
$\endgroup$
-
$\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
