2026-07-20T14:53:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24169 2025-11-12T13:34:00Z ddc:004 open_access

The Complexity of Reachability Problems in Strongly Connected Finite Automata Kiefer, Stefan Ryzhikov, Andrew unambiguous automata nonnegative matrices irreducible matrix sets strongly connected automata matrix monoids mortality completeness synchronisation ergodicity Several reachability problems in finite automata, such as completeness of NFAs and synchronisation of total DFAs, correspond to fundamental properties of sets of nonnegative matrices. In particular, the two mentioned properties correspond to matrix mortality and ergodicity, which ask whether there exists a product of the input matrices that is equal to, respectively, the zero matrix and a matrix with a column of strictly positive entries only. The case where the input automaton is strongly connected (that is, the corresponding set of nonnegative matrices is irreducible) frequently appears in applications and often admits better properties than the general case. In this paper, we address the existence of such properties from the computational complexity point of view, and develop a versatile technique to show that several NL-complete problems remain NL-complete in the strongly connected case. In particular, we show that deciding if a binary total DFA is synchronising is NL-complete even if it is promised to be strongly connected, and that deciding completeness of a binary unambiguous NFA with very limited nondeterminism is NL-complete under the same promise. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Stefan Kiefer and Andrew Ryzhikov 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.62 urn:nbn:de:0030-drops-241690 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.62 eng https://creativecommons.org/licenses/by/4.0/legalcode