dc.contributor.author | Egri-Nagy, A. | |
dc.contributor.author | Nehaniv, C.L. | |
dc.date.accessioned | 2011-04-07T11:26:05Z | |
dc.date.available | 2011-04-07T11:26:05Z | |
dc.date.issued | 2011 | |
dc.identifier.citation | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6482 pp.115-124 | en_US |
dc.identifier.isbn | 978-364218097-2 | |
dc.identifier.issn | 0302-9743 | |
dc.identifier.other | 905165 | |
dc.identifier.uri | http://dx.doi.org/10.1007/978-3-642-18098-9_13 | |
dc.identifier.uri | http://hdl.handle.net/2299/5576 | |
dc.description | “The original publication is available at www.springerlink.com”. Copyright Springer | en_US |
dc.description.abstract | 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. | en_US |
dc.language.iso | en | en_US |
dc.publisher | Springer | en_US |
dc.subject | Cayley graphs | en_US |
dc.subject | finite transformations | en_US |
dc.subject | hierarchical decompositions | en_US |
dc.subject | identity transformations | en_US |
dc.subject | loop-free paths | en_US |
dc.subject | practical calculation | en_US |
dc.subject | semi-group | en_US |
dc.subject | transformation semigroups | en_US |
dc.title | On straight words and minimal permutators in finite transformation semigroups. | en_US |
dc.type | Article | en_US |
herts.preservation.rarelyaccessed | true | |