Piecewise testabiity

Piecewise testabiity.

Simon had proved that
A language is piecewise testable iff its syntactic monoid is J-trivial (meaning that distinct elements of monoid generate distinct ideals).

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.

next