As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
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.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.