×

zbMATH — the first resource for mathematics

Varieties of finite categories. (English) Zbl 0608.18002
The paper develops a theory of finitely generated categories with finitely many objects. The theory generalizes a notion of pseudovarieties given by P. M. Schützenberger and S. Eilenberg. The motivation is to provide stronger tools for investigations of finite-state machines and combinatorial properties of languages. Several interesting results are presented, for instance, the decidability problem - asking whether for given monoids S,T and a pseudovariety W of monoids, there exists a monoid \(X\in W\) such that S is divided by the wreath product of X and T - is reduced to the decidability of the membership problem for W.
Reviewer: V.Koubek

MSC:
18B20 Categories of machines, automata
68Q70 Algebraic theory of languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
20M07 Varieties and pseudovarieties of semigroups
08C15 Quasivarieties
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] 1. J. A. BRZOZOWSKI, Hierarchies of Aperiodic Languages, RAIRO Informatique Théorique, Vol. 10, 1976, pp. 35-49. MR428813
[2] 2. J. A. BRZOZOWSKI and I. SIMON, Characterization of Locally Testable Events, Discrete Math., Vol. 4, 1973, pp. 243-271. Zbl0255.94032 MR319404 · Zbl 0255.94032
[3] 3. S. EILENBERG, Automata, Languages and Machines, Vol. B., Academic Press, New York, 1976. Zbl0359.94067 MR530383 · Zbl 0359.94067
[4] 4. R. KNAST, A Semigroup Characterization of Dot-Depth One Languages, RAIRO Informatique Théorique, 1984. Zbl0522.68063 MR743892 · Zbl 0522.68063
[5] 5. J. E. PIN, On the Semidirect Product of Two Semilattices, Semigroup Forum, Vol. 28, 1984, pp. 73-81. Zbl0527.20046 MR729653 · Zbl 0527.20046
[6] 6. J. E. PIN, H. STRAUBING and D. THÉRIEN, Locally Trivial Categories and Unambiguous Concatenation, submitted for publication, 1985. Zbl0645.20046 · Zbl 0645.20046
[7] 7. J. RHODES, A Homomorphism Theorem for Finite Semigroups, Math. Syst. Th., Vol. 1, 1967, pp. 289-304. Zbl0204.03303 MR223473 · Zbl 0204.03303
[8] 8. J. RHODES and B. TILSON, The Two-Sided Paper, unpublished manuscript, 1984.
[9] 9. D. THÉRIEN, Classification of Finite Monoids : the Language Approach, Theoretical Computer Science, Vol. 14, 1981, pp. 195-208. Zbl0471.20055 MR614416 · Zbl 0471.20055
[10] 10. B. TILSON, Categories as Algebras, an Essential Ingredient in the Theory of Semigroups, in preparation. · Zbl 0627.20031
[11] 11. D. THÉRIEN and M. SZNAJDER-GLODOWSKI, Finite Categories and Regular Languages, Technical report SOCS-85-25, Mcgill University, 1985. · Zbl 0761.68065
[12] 12. D. THÉRIEN and A. WEISS, Graph Congruences and Wreath Products, J. P. Ap. Alg., Vol. 36, 1985. Zbl0559.20042 MR787173 · Zbl 0559.20042
[13] 13. A. WEISS, Varieties of Graph-Congruences, Ph. D. Thesis, McGill University, 1984.
[14] 14. A. WEISS, The Local and Global Varieties Induced by Nilpotent Monoids, RAIRO Informatique Théorique, Vol. 20, n^\circ 3, 1986, pp. 339-355. Zbl0607.20035 MR894718 · Zbl 0607.20035
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.