×

zbMATH — the first resource for mathematics

The loop problem for Rees matrix semigroups. (English) Zbl 1142.20034
Let \(M\) be a monoid with set of generators \(\sigma\colon X^*\to M\), \(\overline X=\{\overline x\mid x\in X\}\) a set of formal inverses for the generators; \(\widehat X=X\cup\overline X\). The (right) loop automaton \(\widehat\Gamma_\sigma(M)\) is obtained from the (right) Cayley graph \(\Gamma_\sigma(M)\) by adding for each edge with label \(x\) an edge in the opposite direction labeled \(\overline x\); the start and the finite state is the identity of \(M\). The (right) loop problem is the language \(L_\sigma(M)\subseteq\widehat X^*\) recognised by the automaton \(\widehat\Gamma_\sigma(M)\).
It is shown that a finitely generated completely zero-simple semigroup has context-free loop problem iff its maximal subgroups are virtually free, i.e., have a free subgroup of finite index.

MSC:
20M05 Free semigroups, generators and relations, word problems
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ayik, H., Ruškuc, N.: Generators and relations of Rees matrix semigroups. Proc. Edinb. Math. Soc. 42, 481–495 (1999) · Zbl 0946.20030
[2] Belegradek, O.V.: Higman’s embedding theorem in a general setting and its application to existentially closed algebras. Notre Dame J. Form. Log. 37(4), 613–624 (1996) · Zbl 0882.03036
[3] Belyaev, V.Y.: Imbeddability of recursively defined inverse semigroups in finitely presented semigroups. Sib. Mat. Zh. 25(2), 50–54 (1984) · Zbl 0554.58014
[4] Boone, W.W., Higman, G.: An algebraic characterization of groups with soluble word problem. J. Aust. Math. Soc. 18, 41–53 (1974). Collection of articles dedicated to the memory of Hanna Neumann, IX · Zbl 0303.20028
[5] Clifford, A.H., Preston, G.B.: The Algebraic Theory of Semigroups, vol. I. Am. Math. Soc., Providence (1961) · Zbl 0111.03403
[6] Dehn, M.: Über unendliche diskontinuierliche Gruppen. Math. Ann. 71(1), 116–144 (1911) · JFM 42.0508.03
[7] Descalço, L., Ruškuc, N.: On automatic Rees matrix semigroups. Commun. Algebra 30, 1207–1226 (2002) · Zbl 1012.20052
[8] Dunwoody, M.J.: The accessibility of finitely presented groups. Invent. Math. 81(3), 449–457 (1985) · Zbl 0572.20025
[9] Elder, M., Kambites, M., Ostheimer, G.: On groups and counter automata. arXiv:math.RA/0611188 (2006) · Zbl 1171.20021
[10] Herbst, T.: On a subclass of context-free groups. RAIRO Inf. Théor. Appl. 25(3), 255–272 (1991) · Zbl 0751.68040
[11] Holt, D.F., Rees, S., Röver, C.E., Thomas, R.M.: Groups with context-free co-word problem. J. Lond. Math. Soc. (2) 71(3), 643–657 (2005) · Zbl 1104.20033
[12] Hopcroft, J.E., Ullman, J.D.: Formal Languages and their Relation to Automata. Addison-Wesley, Reading (1969) · Zbl 0196.01701
[13] Howie, J.M.: Fundamentals of Semigroup Theory. Clarendon, Oxford (1995) · Zbl 0835.20077
[14] Kambites, M.: The loop problem for monoids and semigroups. Math. Proc. Camb. Philos. Soc. (to appear) · Zbl 1144.20036
[15] Kambites, M.: Presentations for semigroups and semigroupoids. Int. J. Algebra Comput. 15, 291–308 (2005) · Zbl 1072.20065
[16] Kambites, M.: Automatic semigroups and categories. Theor. Comput. Sci. 353, 272–290 (2006) · Zbl 1095.20032
[17] Kambites, M.: Word problems recognisable by deterministic blind monoid automata. Theor. Comput. Sci. 362(1), 232–237 (2006) · Zbl 1100.68051
[18] Kharlampovich, O.G., Sapir, M.V.: Algorithmic problems in varieties. Int. J. Algebra Comput. 5(4–5), 379–602 (1995) · Zbl 0837.08002
[19] Kublanovskiĭ, S.I.: On varieties of associative algebras with local finiteness conditions. Algebra Analiz 9(4), 119–174 (1997)
[20] Kukin, G.: The variety of all rings has Higman’s property. In: Algebra and Analysis, Irkutsk, 1989. Am. Math. Soc. Transl. Ser. 2, vol. 163, pp. 91–101. Am. Math. Soc., Providence (1995) · Zbl 0838.16014
[21] Lawson, M.V.: Rees matrix semigroups over semigroupoids and the structure of a class of abundant semigroups. Acta Sci. Math. 66, 517–540 (2000) · Zbl 0973.20056
[22] Lawson, M.V.: Finite Automata. Chapman and Hall, London (2003)
[23] McAlister, D.B.: Rees matrix covers for locally inverse semigroups. Trans. Am. Math. Soc. 227, 727–738 (1983) · Zbl 0516.20039
[24] Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. J. Comput. Syst. Sci. 26(3), 295–310 (1983) · Zbl 0537.20011
[25] Murskiĭ, V.L.: Isomorphic imbeddability of a semigroup with an enumerable set of defining relations into a finitely presented semigroup. Mat. Zamet. 1, 217–224 (1967)
[26] Petrich, M.: Embedding semigroups into idempotent generated ones. Monatsh. Math. 141(4), 315–322 (2004) · Zbl 1075.20025
[27] Pin, J.-E.: Varieties of Formal Languages. North Oxford Academic (1986) · Zbl 0632.68069
[28] Rees, D.: On semi-groups. Proc. Camb. Philos. Soc. 36, 387–400 (1940) · JFM 66.1207.01
[29] Stewart, I.A., Thomas, R.M.: Formal languages and the word problem for groups. In: Groups St. Andrews 1997 in Bath, II. London Math. Soc. Lecture Note Ser., vol. 261, pp. 689–700. Cambridge Univ. Press, Cambridge (1999) · Zbl 0936.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.