Both nondeterministic and deterministic finite automata (NFA and DFA) recognize exactly the regular languages. However, converting an NFA to an equivalent DFA incurs an exponential blow-up in the number of states which can not be avoided in worth case. Yet, the impact of nondeterminism on the size of other models of regular languages remains less understood.

A prominent instance is two-way automata, which allow the head to move both leftward and rightward. While both deterministic (2DFA) and nondeterministic (2NFA) versions recognize the regular languages, the precise cost of simulating a 2NFA with a 2DFA has remained a longstanding open problem in the field of descriptional complexity since 1978, known as the Sakoda-Sipser question.

In this talk, we briefly present this problem and introduce a novel form of nondeterminism called the common guess. In an automaton equipped with common guess (2DFA+cg for short), before computation begins, the machine nondeterministically annotates each symbol of the input word. It then processes the input deterministically as a 2DFA, using both the original symbols and their annotations. While this approach does not extend expressive power beyond regular languages, we show that it significantly improves succinctness compared to standard 2NFAs.

Additionally, we compare this model with another representation of regular lan- guages, namely 1-limited automata. We discuss how the common guess model is positioned between 1-limited automata and their deterministic counterparts, offering new insights into the relationship between nondeterminism and deter- minism in automata theory.