TY - GEN
T1 - k-universality of regular languages
AU - Adamson, Duncan
AU - Fleischmann, Pamela
AU - Huch, Annika
AU - Koß, Tore
AU - Manea, Florin
AU - Nowotka, Dirk
N1 - Duncan Adamson’s work was funded by the Leverhulme Trust via the Leverhulme Research Centre for Functional Material Design. Tore Koß’s work was supported by the DFG project number 389613931. Florin Manea’s work was supported by the DFG Heisenberg-project number 466789228.
PY - 2023/12
Y1 - 2023/12
N2 - A subsequence of a word w is a word u such that u = w[i1]w[i2] . . . w[ik], for some set of indices 1 ≤ i1 < i2 < · · · < ik ≤ |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.
AB - A subsequence of a word w is a word u such that u = w[i1]w[i2] . . . w[ik], for some set of indices 1 ≤ i1 < i2 < · · · < ik ≤ |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.
KW - Finite Automata
KW - Regular Languages
KW - String Algorithms
KW - Subsequences
U2 - 10.4230/LIPIcs.ISAAC.2023.4
DO - 10.4230/LIPIcs.ISAAC.2023.4
M3 - Conference contribution
AN - SCOPUS:85179139394
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Algorithms and Computation, ISAAC 2023
A2 - Iwata, Satoru
A2 - Kakimura, Naonori
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Algorithms and Computation, ISAAC 2023
Y2 - 3 December 2023 through 6 December 2023
ER -