×

zbMATH — the first resource for mathematics

On straight words and minimal permutators in finite transformation semigroups. (English) Zbl 1297.68173
Domaratzki, Michael (ed.) et al., Implementation and application of automata. 15th international conference, CIAA 2010, Winnipeg, MB, Canada, August 12–15, 2010. Revised selected papers. Berlin: Springer (ISBN 978-3-642-18097-2/pbk). Lecture Notes in Computer Science 6482, 115-124 (2011).
Summary: 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.
For the entire collection see [Zbl 1206.68008].

MSC:
68Q70 Algebraic theory of languages and automata
20M20 Semigroups of transformations, relations, partitions, etc.
20M35 Semigroups in automata theory, linguistics, etc.
68R15 Combinatorics on words
Software:
GAP; Krohn-Rhodes; SgpDec
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Egri-Nagy, A., Nehaniv, C.L.: Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes Theory. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 315–316. Springer, Heidelberg (2005) · Zbl 1115.68429 · doi:10.1007/978-3-540-30500-2_32
[2] Egri-Nagy, A., Nehaniv, C.L.: Cycle structure in automata and the holonomy decomposition. Acta Cybernetica 17, 199–211 (2005) ISSN: 0324-721X · Zbl 1104.68060
[3] Egri-Nagy, A., Nehaniv, C.L.: Algebraic properties of automata associated to Petri nets and applications to computation in biological systems. BioSystems 94(1-2), 135–144 (2008) · doi:10.1016/j.biosystems.2008.05.019
[4] Egri-Nagy, A., Nehaniv, C.L.: SgpDec – software package for hierarchical coordinatization of groups and semigroups, implemented in the GAP computer algebra system, Version 0.5.24+ (2010), http://sgpdec.sf.net
[5] Ganyushkin, O., Mazorchuk, V.: Classical Transformation Semigroups. Algebra and Applications. Springer, Heidelberg (2009) · Zbl 1166.20056 · doi:10.1007/978-1-84800-281-4
[6] The GAP Group: GAP – Groups, Algorithms, and Programming, Version 4.4 (2006), http://www.gap-system.org
[7] Kastan, M.B., Kuerbitz, S.J.: Control of G1 arrest after DNA damage. Environ. Health Perspect. 101(Suppl. 5), 55–58 (1993)
[8] Krohn, K., Rhodes, J.L., Tilson, B.R.: The prime decomposition theorem of the algebraic theory of machines. In: Arbib, M.A. (ed.) Algebraic Theory of Machines, Languages, and Semigroups, ch. 5, pp. 81–125. Academic Press, London (1968)
[9] Rhodes, J.: Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Biology, Physics, Psychology, Philosophy and Games. World Scientific Press, Singapore (2009) · doi:10.1142/7107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.