P=NP for some structures over the binary words

Over the universe of binary words, {0,1}*, a type of structures of finite signature is defined that satisfy P=NP. This holds true both for the related classes of programs in which tests of equality (identity) of words are allowed, as well as for those in which no equality tests occur. The related structures correspond essentially to the pushdown data structures enriched by predicates which are suitably padded PSPACE-complete word sets.