×

zbMATH — the first resource for mathematics

Locally trivial categories and unambiguous concatenation. (English) Zbl 0645.20046
Authors’ summary: “We use the recently developed theory of finite categories and the two-sided kernel to study the effect of the unambiguous concatenation product of recognizable languages on the syntactic monoids of the languages involved. As a result of this study we obtain an algebraic characterization (originally due to Pin) of the closure of a variety of languages under boolean operations and unambiguous concatenation, and a new proof of a theorem of Straubing characterizing the closure of a variety of languages under boolean operations and concatenation. We also note some connections to the study of the dot-depth hierarchy.”
Reviewer: B.Pondělíček

MSC:
20M35 Semigroups in automata theory, linguistics, etc.
20M50 Connections of semigroups with homological algebra and category theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Eilenberg, S., Automata, languages and machines, vol. B, (1976), Academic Press New York
[2] Pin, J.E., Propriétés syntactiques du produit non ambigu. 7th ICALP, (), 483-499
[3] Pin, J.-E., Variétés de langages et variétés de semigroupes, () · Zbl 0398.68035
[4] Pin, J.-E., Varieties of formal languages, (1986), North Oxford, London, and Plenum New York · Zbl 0632.68069
[5] Rhodes, J., A homomorphism theorem for finite semigroups, Math. systems theory, 1, 289-304, (1967) · Zbl 0204.03303
[6] Rhodes, J.; Tilson, B., The kernel of monoid morphisms, (1986), Preprint
[7] J. Rhodes and P. Weil, Decomposition techniques for finite semigroups, Part 2, to appear. · Zbl 0684.20055
[8] Schützenberger, M.P., Sur le produit de concatenation non ambigu, Semigroup forum, 13, 47-75, (1976) · Zbl 0373.20059
[9] Straubing, H., Aperiodic homomorphisms and the concatenation product of recognizable sets, J. pure appl. algebra, 15, 319-327, (1979) · Zbl 0407.20056
[10] Straubing, H., Relational morphisms and operations on recognizable sets, RAIRO inform. théor., 15, 149-159, (1981) · Zbl 0463.20049
[11] Straubing, H., Finite semigroup varieties of the form V∗{\bfd}, J. pure appl. algebra, 36, 53-94, (1985) · Zbl 0561.20042
[12] Thomas, W., Classifying regular events in symbolic logic, J. comput. system. sci., 25, 360-376, (1982) · Zbl 0503.68055
[13] Tilson, B., Categories as algebra: an essential ingredient in the theory of monoids, J. pure appl. algebra, 48, 83-198, (1987) · Zbl 0627.20031
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.