2026-07-23T10:34:46Z https://drops.dagstuhl.de/oai

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

Minimization of Deterministic Finite Automata Modulo the Edit Distance Michaliszyn, Jakub Otop, Jan automata theory automata minimization edit distance We propose a novel approach to minimization of deterministic finite automata (DFA), in which the DFA is further minimized at the expense of relaxing equality of languages to merely a similarity. As the notion of similarity of languages, we consider the edit distance between languages ℒ, ℒ', i.e., the minimal number of edits necessary to transform any word from ℒ to some word from ℒ' and vice versa. In this paper we address two problems: minimization up to a predetermined edit distance given in the input, and minimization up to a bounded edit distance, in which there has to be an upper bound on the number of edits, but it is not specified. We show the first problem to be PSpace {}-complete and that the second problem is in Σ₂^p, and both NP-hard and coNP-hard. We show that if we limit how many strongly connected components can be visited by a single run (i.e., bounded SCC-depth), the problem becomes NP-complete. We also establish maximal subclasses of DFA over which minimization up to a bounded edit distance can be performed in polynomial time. Additionally, we provide a succinct overview of alternative metrics for assessing language similarity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jakub Michaliszyn and Jan Otop 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.77 urn:nbn:de:0030-drops-241843 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.77 eng https://creativecommons.org/licenses/by/4.0/legalcode