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 -