On automata recognizing birecurrent sets (Q1625603): Difference between revisions

In this contribution birecurrent regular languages are investigated. A regular language $L$ is birecurrent if both the minimal DFA (deterministic finite-state automaton) for $L$ as well as the minimal DFA for the reversal of $L$ are strongly connected. The reversal of a language consists of all the words of the language read backwards. Additionally, a DFA is strongly connected if for every pair of states $p$ and $q$ there exists an input $w$ such that starting in state $p$ reading $w$ causes the DFA to change to state $q$. In other words, the minimal DFA for a birecurrent regular language as well as its reversal are graphs with a single strongly connected component if we disregard the input letters on the transitions. It is demonstrated that it is PSPACE-complete to decide whether a given DFA recognizes a birecurrent language. The difficulty remains for DFA with just two letters in which all states are final, as well as for DFA with just two letters in which each state can process each letter. These results provide answers to questions raised in [\textit{F. Dolce} et al., Int. J. Algebra Comput. 28, No. 4, 613--652 (2018; Zbl 1395.68166)]. Checking the birecurrent property is easily achieved in polynomial space following essentially the definition. The hardness is obtained by means of a reduction from the DFA intersection emptiness problem. The special cases with just two letters are handled by reductions from the general problem. The paper is well written and, though short, provides all necessary details to support its claims. An illustration helps provide additional insight into one of the used reductions. The author only presupposes a very basic background in automata theory and complexity theory, so any graduate computer science student should be able to fully appreciate the contribution.