2026-07-24T10:09:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19306 2024-03-06T11:03:43Z ddc:004 open_access

k-Universality of Regular Languages Adamson, Duncan Fleischmann, Pamela Huch, Annika Koß, Tore Manea, Florin Nowotka, Dirk String Algorithms Regular Languages Finite Automata Subsequences A subsequence of a word w is a word u such that u = w[i₁] w[i₂] … w[i_k], for some set of indices 1 ≤ i₁ < i₂ < … < i_k ≤ |w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ^k appears in w as a subsequence. In this paper, we study the intersection between the set of k-subsequence universal words over some alphabet Σ and regular languages over Σ. We call a regular language L k-∃-subsequence universal if there exists a k-subsequence universal word in L, and k-∀-subsequence universal if every word of L is k-subsequence universal. We give algorithms solving the problems of deciding if a given regular language, represented by a finite automaton recognising it, is k-∃-subsequence universal and, respectively, if it is k-∀-subsequence universal, for a given k. The algorithms are FPT w.r.t. the size of the input alphabet, and their run-time does not depend on k; they run in polynomial time in the number n of states of the input automaton when the size of the input alphabet is O(log n). Moreover, we show that the problem of deciding if a given regular language is k-∃-subsequence universal is NP-complete, when the language is over a large alphabet. Further, we provide algorithms for counting the number of k-subsequence universal words (paths) accepted by a given deterministic (respectively, nondeterministic) finite automaton, and ranking an input word (path) within the set of k-subsequence universal words accepted by a given finite automaton. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Duncan Adamson and Pamela Fleischmann and Annika Huch and Tore Koß and Florin Manea and Dirk Nowotka 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.4 urn:nbn:de:0030-drops-193064 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.4 eng https://creativecommons.org/licenses/by/4.0/legalcode