Bounds on the index and period of a binary relation on a finite set. (English) Zbl 0353.20055


20M20 Semigroups of transformations, relations, partitions, etc.
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI EuDML


[1] Birkhoff, G., Lattice Theory, AMS Colloq. Publ. Vol XXV, Providence, RI, 1967. · Zbl 0153.02501
[2] Brandon, R. L.; Hardy, D. W.; Markowsky, G., The Schützenberger Group of an H-class in the Semigroup of Binary Relations, Semigroup Forum, 5, 45-53 (1972) · Zbl 0259.20056 · doi:10.1007/BF02572873
[3] Clifford, A.H. and G.B. Preston, The Algebraic Theory of Semigroups, AMS Surveys, Vol. I, Providence, RI, 1961. · Zbl 0111.03403
[4] Hopcroft, J. E.; Ullman, J. D., Formal Languages and Their Relation to Automata (1969), Reading, MA: Addison-Wesley, Reading, MA · Zbl 0196.01701
[5] Landau, E., Handbuch Verteilung der Primzahlen, 1, 222-229 (1909)
[6] Mandl, R., Precise Bounds Associated With the Subset Construction on Various Classes of Nondeterministic Finite Automata, Proc. 7th Annual Princeton Conf. on Info. Sciences and Systems, 1973, 263-267.
[7] Moore, F.R., On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Automata, IEEE Trans. on Computers 20, 1211-1214 · Zbl 0229.94033
[8] Schein, B. M., Remarks on Research Problem T45, Semigroup Forum, Vol. 4, p. 373.
[9] Zaretskii, K. A., The Semigroup of Binary Relations, Mat. Sbornik, 61, 291-305 (1963) · Zbl 0125.28003
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.