Deciding k-piecewise testability
Ondřej Klíma, Michal Kunc, Libor Polák · International Journal of Algebra and Computation · 2026
Piecewise testability of a regular language can be decided by checking whether its minimal deterministic automaton contains no nontrivial cycles and whether for every subset of the input alphabet, all computations on words over this subalphabet are confluent. In this paper, it is proved that if such an automaton contains no simple path of length greater than [Formula: see text], then the accepted language is [Formula: see text]-piecewise testable. Furthermore, it is proved that the problem of deciding [Formula: see text]-piecewise testability of regular languages given by deterministic finite automata is coNP-complete for every [Formula: see text], while this problem is known to be solvable in polynomial time for [Formula: see text].