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 -