Simon had proved that
A language is piecewise testable iff its syntactic monoid is
J-trivial (meaning that distinct elements of monoid generate
Stern modified these necessary and sufficient conditions
and described a polynomial time algorithm to verify piecewise testability.
The algorithm was implemented by Caron.
We use in our package an algorithm to verify piecewise testability of
deterministic finite automaton of order O(n2).
In comparison, Stern's algorithm for piecewise testability
implemented by Caron has worst-case complexity O(n5).
The parameter n is here the sum of number of states
and number of edges of the state transition graph of the
automaton (n can be also considered as the product of the number of
states by the size of the alphabet).
We implement also an algorithm to verify piecewise testability of
a finite semigroup of order O(n2) where n is the size
of the semigroup.