×

zbMATH — the first resource for mathematics

On graph products of automatic monoids. (English) Zbl 1019.20028
Free products and direct products of monoids are particular cases of graph products of monoids. It is known that free products and direct products of automatic monoids are automatic. This paper extends these results to graph products for two classes of automatic monoids: the automatic monoids of finite geometric type, and the prefix-automatic monoids.

MSC:
20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
PDF BibTeX Cite
Full Text: DOI Numdam EuDML
References:
[1] C.M. Campbell , E.F. Robertson , N. Ruskuc and R.M. Thomas , Automatic Semigroups . Theoret. Comput. Sci. (to appear). MR 1795250 | Zbl 0987.20033 · Zbl 0987.20033
[2] A.J. Duncan , E.F. Robertson and N. Ruskuc , Automatic monoids and change of generators . Math. Proc. Cambridge Philos. Soc. 127 ( 1999 ) 403 - 409 . MR 1713118 | Zbl 0941.20065 · Zbl 0941.20065
[3] E.R. Green , Graph Products of Groups , Ph.D. Thesis. The University of Leeds ( 1990 ). · Zbl 0723.73037
[4] J.E. Hopcroft and J.D. Ullman , Introduction to Automata Theory , Languages and Computation. Addison-Wesley ( 1979 ). MR 645539 | Zbl 0426.68001 · Zbl 0426.68001
[5] S. Hermiller and J. Meier , Algorithms and Geometry for Graph Products of Groups . J. Algebra 171 ( 1995 ) 230 - 257 . MR 1314099 | Zbl 0831.20032 · Zbl 0831.20032
[6] J.M. Howie , An Introduction to Semigroup Theory . Academic Press ( 1976 ). MR 466355 | Zbl 0355.20056 · Zbl 0355.20056
[7] P.V. Silva and B. Steinberg , A Geometric Characterization of Automatic Monoids . Universidade do Porto (preprint). MR 2082097 | Zbl 1076.20041 · Zbl 1076.20041
[8] P.V. Silva and B. Steinberg , Extensions and Submonoids of Automatic Monoids . Universidade do Porto (preprint). MR 1932918 | Zbl 1061.20048 · Zbl 1061.20048
[9] A. Veloso da Costa , Graph Products of Monoids . Semigroup Forum 63 ( 2001 ) 247 - 277 . MR 1830687 | Zbl 0992.20042 · Zbl 0992.20042
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.