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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community