×

Rational subsets and submonoids of wreath products. (English) Zbl 1332.20038

Summary: It is shown that membership in rational subsets of wreath products \(H\wr V\) with \(H\) a finite group and \(V\) a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product \(\mathbb Z\wr\mathbb Z\) with an undecidable membership problem.

MSC:

20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20E22 Extensions, wreath products, and other compositions of groups
20M05 Free semigroups, generators and relations, word problems
03B25 Decidability of theories and sets of sentences
03D35 Undecidability and degrees of sets of sentences
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of languages and automata
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Anisimov, A. V., Group languages, Kibernetika. Kibernetika, Cybernetics, 4, 594-601 (1973), (in Russian); English translation in
[2] Benois, M., Parties rationnelles du groupe libre, C. R. Acad. Sci. Paris, Sér. A, 269, 1188-1190 (1969) · Zbl 0214.03903
[3] Bucher, W.; Ehrenfeucht, A.; Haussler, D., On total regulators generated by derivation relations, Theor. Comput. Sci., 40, 131-148 (1985) · Zbl 0606.68074
[4] Cano, A.; Guaiana, G.; Pin, J.-É., Regular languages and partial commutations, Inf. Comput., 230, 76-96 (2013) · Zbl 1358.68202
[5] Chambart, P.; Schnoebelen, P., Post embedding problem is not primitive recursive, with applications to channel systems, (Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science. Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007. Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science. Proceedings of the 27th International Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007, Lecture Notes in Computer Science, vol. 4855 (2007), Springer), 265-276 · Zbl 1136.03030
[6] Cleary, S., Distortion of wreath products in some finitely-presented groups, Pac. J. Math., 228, 1, 53-61 (2006) · Zbl 1150.20030
[7] Davis, T. C.; Olshanskii, A. Y., Subgroup distortion in wreath products of cyclic groups, J. Pure Appl. Algebra, 215, 12, 2987-3004 (2011) · Zbl 1259.20049
[8] Dehn, M., Über unendliche diskontinuierliche gruppen, Math. Ann., 71, 116-144 (1911), (in German) · JFM 42.0508.03
[9] Diekert, V.; Muscholl, A., Solvability of equations in free partially commutative groups is decidable, Int. J. Algebra Comput., 16, 6, 1047-1069 (2006) · Zbl 1112.03009
[10] Ehrenfeucht, A.; Haussler, D.; Rozenberg, G., On regularity of context-free languages, Theor. Comput. Sci., 27, 311-332 (1983) · Zbl 0553.68044
[11] Eilenberg, S.; Schützenberger, M. P., Rational sets in commutative monoids, J. Algebra, 13, 173-191 (1969) · Zbl 0206.02703
[12] Fernau, H.; Stiebe, R., Sequential grammars and automata with valences, Theor. Comput. Sci., 276, 1-2, 377-405 (2002) · Zbl 1002.68079
[13] Finkel, A.; Schnoebelen, P., Well-structured transition systems everywhere!, Theor. Comput. Sci., 256, 1-2, 63-92 (2001) · Zbl 0973.68170
[14] Gilman, R. H., Formal languages and infinite groups, (Geometric and Computational Perspectives on Infinite Groups. Geometric and Computational Perspectives on Infinite Groups, Minneapolis, MN and New Brunswick, NJ, 1994. Geometric and Computational Perspectives on Infinite Groups. Geometric and Computational Perspectives on Infinite Groups, Minneapolis, MN and New Brunswick, NJ, 1994, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 25 (1996), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 27-51 · Zbl 0851.20030
[15] Grunschlag, Z., Algorithms in geometric group theory (1999), University of California at Berkley, PhD thesis
[16] Haines, L. H., On free monoids partially ordered by embedding, J. Comb. Theory, 6, 94-98 (1969) · Zbl 0224.20065
[17] Higman, G., Ordering by divisibility in abstract algebras, Proc. Lond. Math. Soc., 2, 326-336 (1952) · Zbl 0047.03402
[18] Jurdzinski, T., Leftist grammars are non-primitive recursive, (Proceedings of the 35th International Colloquium on Automata, Languages and Programming. Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008. Proceedings of the 35th International Colloquium on Automata, Languages and Programming. Proceedings of the 35th International Colloquium on Automata, Languages and Programming, ICALP 2008, Lecture Notes in Computer Science, vol. 5126 (2008), Springer), 51-62 · Zbl 1155.68411
[19] Kambites, M., Formal languages and groups as memory, Commun. Algebra, 37, 1, 193-208 (2009) · Zbl 1163.68029
[20] Kambites, M.; Silva, P. V.; Steinberg, B., On the rational subset problem for groups, J. Algebra, 309, 2, 622-639 (2007) · Zbl 1123.20047
[21] Kunc, M., Regular solutions of language inequalities and well quasi-orders, Theor. Comput. Sci., 348, 2, 277-293 (2005) · Zbl 1081.68047
[22] Kuske, D.; Lohrey, M., Logical aspects of Cayley-graphs: the group case, Ann. Pure Appl. Log., 131, 1-3, 263-286 (2005) · Zbl 1063.03005
[23] Lohrey, M.; Sénizergues, G., Theories of HNN-extensions and amalgamated products, (Bugliesi, M.; Preneel, B.; Sassone, V.; Wegener, I., Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Venice (Italy). Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006, Venice (Italy), Lecture Notes in Computer Science, vol. 4052 (2006), Springer), 681-692 · Zbl 1134.03009
[24] Lohrey, M.; Steinberg, B., The submonoid and rational subset membership problems for graph groups, J. Algebra, 320, 2, 728-755 (2008) · Zbl 1156.20052
[25] Lohrey, M.; Steinberg, B., Submonoids and rational subsets of groups with infinitely many ends, J. Algebra, 324, 4, 970-983 (2010) · Zbl 1239.20038
[26] Lohrey, M.; Steinberg, B., Tilings and submonoids of metabelian groups, Theory Comput. Syst., 48, 2, 411-427 (2011) · Zbl 1229.20025
[27] Lohrey, M.; Steinberg, B.; Zetzsche, G., Rational subsets and submonoids of wreath products, (Fomin, F. V.; Freivalds, R.; Kwiatkowska, M. Z.; Peleg, D., Automata, Languages, and Programming—40th International Colloquium. Proceedings, Part II. Automata, Languages, and Programming—40th International Colloquium. Proceedings, Part II, ICALP 2013, Riga, Latvia, July 8-12 (2013)), 361-372 · Zbl 1293.20036
[28] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer · Zbl 0368.20023
[29] Minsky, M. L., Computation: Finite and Infinite Machines (1967), Prentice-Hall International: Prentice-Hall International Englewood Cliffs · Zbl 0195.02402
[30] Motwani, R.; Panigrahy, R.; Saraswat, V. A.; Venkatasubramanian, S., On the decidability of accessibility problems (extended abstract), (Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing. Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, STOC 2000 (2000), ACM), 306-315 · Zbl 1296.68088
[31] Nielsen, J., Om regning med ikke kommutative faktoren og dens anvendelse i gruppeteorien, Mat. Tidsskr. B, 77-94 (1921), (in Danish) · JFM 48.0123.03
[32] Roman’kov, V., On the occurence problem for rational subsets of a group, (Roman’kov, V., International Conference on Combinatorial and Computational Methods in Mathematics (1999)), 76-81
[33] Romanovskiĭ, N. S., Some algorithmic problems for solvable groups, Algebra Log., 13, 1, 26-34 (1974)
[34] Romanovskiĭ, N. S., The occurrence problem for extensions of abelian groups by nilpotent groups, Sib. Mat. Zh., 21, 170-174 (1980)
[35] Sakarovitch, J., Elements of Automata Theory (2009), Cambridge University Press
[36] Schnoebelen, P., Verifying lossy channel systems has nonprimitive recursive complexity, Inf. Process. Lett., 83, 5, 251-261 (2002) · Zbl 1043.68016
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.