# What is the strongest arithmetic theory decidable by a DFA, DPDA or PDA?

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?

• Question: how is going from a DFA to a PDA weakening? Aren’t PDAs capable of recognizing more languages, and therefore stronger? – D. Ben Knoble Jan 26 '20 at 17:14
• @D.BenKnoble I was thinking of "weaker" in a different sense. Question edited. – danportin Jan 26 '20 at 19:30
• 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. – Shaull Jan 26 '20 at 19:38
• @Shaull Right, it's WS1S that's regular. – danportin Jan 26 '20 at 19:49