Deciding k -piecewise testability

Piecewise testability of a regular language can be decided by checking whether its minimal deterministic automaton contains no non-trivial 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 k, then the accepted language is k-piecewise testable. Furthermore, it is proved that the problem of deciding k-piecewise testability of regular languages given by deterministic finite automata is coNP-complete for every k ≥ 4, while this problem is known to be solvable in polynomial time for k ≤ 3.