A special binary representation/coding of an element in a free partially commutative monoid initially introduced in 1980 has been successfully used as a basis for the effective/polynomial solution of the following long standing open problems: functional equivalence of program schemata with non-degenerate operators, equivalence of deterministic multitape finite automata (MFA), equivalence of deterministic multidimensional multitape finite automata (MMFA), regular expressions for MFA, systems of equations for MFA regular sets. In addition, the consideration of the coding leads to an alternative characterization of commutation classes in free partially commutative monoids, which, in comparison with the already known characterization implying from the projection lemma, brings to a better efficiency when checking the equality of traces with lengths longer than a certain number or with alphabets containing more than two symbols. Regular expressions for languages of MFA and MMFA are also defined based on the mentioned coding. A brief overview of relevant AI applications concludes considerations.