Show simple item record

dc.contributor.authorEgri-Nagy, A.
dc.contributor.authorNehaniv, C.L.
dc.date.accessioned2011-04-07T11:26:05Z
dc.date.available2011-04-07T11:26:05Z
dc.date.issued2011
dc.identifier.citationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6482 pp.115-124en_US
dc.identifier.isbn978-364218097-2
dc.identifier.issn0302-9743
dc.identifier.other905165
dc.identifier.urihttp://dx.doi.org/10.1007/978-3-642-18098-9_13
dc.identifier.urihttp://hdl.handle.net/2299/5576
dc.description“The original publication is available at www.springerlink.com”. Copyright Springeren_US
dc.description.abstractMotivated 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.isoenen_US
dc.publisherSpringeren_US
dc.subjectCayley graphsen_US
dc.subjectfinite transformationsen_US
dc.subjecthierarchical decompositionsen_US
dc.subjectidentity transformationsen_US
dc.subjectloop-free pathsen_US
dc.subjectpractical calculationen_US
dc.subjectsemi-groupen_US
dc.subjecttransformation semigroupsen_US
dc.titleOn straight words and minimal permutators in finite transformation semigroups.en_US
dc.typeArticleen_US
herts.preservation.rarelyaccessedtrue


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record