Journalartikel

Jahr der Veröffentlichung: 2011

Seiten: 765-772

Zeitschrift: Theoretical Computer Science

Bandnummer: 412

Heftnummer: 8-10

ISSN: 0304-3975

eISSN: 1879-2294

DOI Link: https://doi.org/10.1016/j.tcs.2010.11.021

Verlag: Elsevier

Abstract: 
The size of the transformation semigroup of a reversible deterministic finite automaton with n states, or equivalently, of a semigroup given by generators of injective partial functions on n objects, had remained unexplored in the case where the set of generators is a pair. We show that in this case, the maximal size is attained by a semigroup generated by a permutation that satisfies a property depending on n and a partial injective mapping whose domain and image both have size n - 1. Moreover, we give precise formulas in terms of n for this maximal size. (C) 2010 Elsevier B.V. All rights reserved.

Harvard-Zitierstil: Beaudry, M. and Holzer, M. (2011) On the size of inverse semigroups given by generators, Theoretical Computer Science, 412(8-10), pp. 765-772. https://doi.org/10.1016/j.tcs.2010.11.021

APA-Zitierstil: Beaudry, M., & Holzer, M. (2011). On the size of inverse semigroups given by generators. Theoretical Computer Science. 412(8-10), 765-772. https://doi.org/10.1016/j.tcs.2010.11.021