TY - GEN

T1 - On straight words and minimal permutators in finite transformation semigroups

AU - Egri-Nagy, Attila

AU - Nehaniv, Chrystopher L.

PY - 2011/2/21

Y1 - 2011/2/21

N2 - Motivated by issues arising in computer science, we investigate the loop-free paths from the identity transformation and corresponding straight words in the Cayley graph of a finite transformation semigroup with a fixed generator set. Of special interest are words that permute a given subset of the state set. Certain such words, called minimal permutators, are shown to comprise a code, and the straight ones comprise a finite code. Thus, words that permute a given subset are uniquely factorizable as products of the subset's minimal permutators, and these can be further reduced to straight minimal permutators. This leads to insight into structure of local pools of reversibility in transformation semigroups in terms of the set of words permuting a given subset. These findings can be exploited in practical calculations for hierarchical decompositions of finite automata. As an example we consider groups arising in biological systems.

AB - Motivated by issues arising in computer science, we investigate the loop-free paths from the identity transformation and corresponding straight words in the Cayley graph of a finite transformation semigroup with a fixed generator set. Of special interest are words that permute a given subset of the state set. Certain such words, called minimal permutators, are shown to comprise a code, and the straight ones comprise a finite code. Thus, words that permute a given subset are uniquely factorizable as products of the subset's minimal permutators, and these can be further reduced to straight minimal permutators. This leads to insight into structure of local pools of reversibility in transformation semigroups in terms of the set of words permuting a given subset. These findings can be exploited in practical calculations for hierarchical decompositions of finite automata. As an example we consider groups arising in biological systems.

UR - http://www.scopus.com/inward/record.url?scp=79951644454&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18098-9_13

DO - 10.1007/978-3-642-18098-9_13

M3 - Conference contribution

AN - SCOPUS:79951644454

SN - 9783642180972

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 115

EP - 124

BT - Implementation and Application of Automata - 15th International Conference, CIAA 2010, Revised Selected Papers

T2 - 15th International Conference on Implementation and Application of Automata, CIAA 2010

Y2 - 12 August 2010 through 15 August 2010

ER -