On straight words and minimal permutators in finite transformation semigroups

DOI10.1007/978-3-642-18098-9_13zbMATH Open1297.68173arXiv1002.2793OpenAlexW1880280254MaRDI QIDQ3073628FDOQ3073628

Authors: Attila Egri-Nagy, Chrystopher L. Nehaniv 

Publication date: 11 February 2011

Published in: Implementation and Application of Automata (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1002.2793

Recommendations

• scientific article; zbMATH DE number 1537527
• scientific article; zbMATH DE number 1376752
• On factorisations and generators in transformation semigroups.
• Some problems on groups of finite automatic permutations
• Near permutation semigroups.

Mathematics Subject Classification ID

Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic theory of languages and automata (68Q70) Combinatorics on words (68R15) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Classical finite transformation semigroups. An introduction.
• Cycle structure in automata and the holonomy decomposition
• Implementation and Application of Automata

Cited In (2)

• Symmetry structure in discrete models of biochemical systems: natural subsystems and the weak control hierarchy in a new model of computation driven by interactions
• Lower bounds on words separation: are there short identities in transformation semigroups?

Uses Software

• GAP
• SgpDec
• Krohn-Rhodes

This page was built for publication: On straight words and minimal permutators in finite transformation semigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073628)