On finitely generated submonoids of virtually free groups

DOI10.1515/GCC-2018-0008MaRDI QIDQ2317164zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 8 August 2019

Published in Groups - Complexity - Cryptology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.07746

zbMATH Keywords

decidabilityfree groupsubmonoidsKleene monoidsrational monoidvirtually free groupgraded monoid

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free nonabelian groups (20E05) Algebraic theory of languages and automata (68Q70) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: We prove that it is decidable whether or not a finitely generated submonoid of a virtually free group is graded, introduce a new geometric characterization as quasi-geodesic monoids, and show that their word problem is rational (as a relation). We also solve the isomorphism problem for this class of monoids, generalizing earlier results for submonoids of free monoids. We also prove that the classes of graded monoids, regular monoids and Kleene monoids coincide for submonoids of free groups.

Recommendations

• ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
• Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness
• The submonoid and rational subset membership problems for graph groups.
• On deciding whether a monoid is a free monoid or is a group

Cites work

• scientific article; zbMATH DE number 1820023 (Why is no real title available?)
• scientific article; zbMATH DE number 3138253 (Why is no real title available?)
• scientific article; zbMATH DE number 3911744 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1385418 (Why is no real title available?)
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• A note on decidability questions on presentations of word semigroups
• Context-Free Groups and Bass–Serre Theory
• Easy multiplications. I: The realm of Kleene's theorem
• Easy multiplications. II: Extensions of rational semigroups
• Elements of automata theory. Translated from the French by Reuben Thomas
• Geometric characterizations of virtually free groups
• Groups, the theory of ends, and context-free languages
• On Cayley graphs of virtually free groups.
• On commutative Kleene monoids
• On torsion-free groups with infinitely many ends
• Rational equivalence relations
• Stallings foldings and subgroups of free groups
• Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness
• The homomorphism problem for the free monoid
• Topology of finite graphs

Cited in

(7)

• Virtual finite quotients of finitely generated groups
• Subsemigroups of virtually free groups: finite Malcev presentations and testing for freeness
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• Every finitely generated submonoid of a free monoid has a finite Malcev's presentation
• Monomorphisms of finitely generated free groups have finitely generated equalizers
• ALGORITHMIC PROBLEMS ON INVERSE MONOIDS OVER VIRTUALLY FREE GROUPS
• Combinatorial classification of finitely generated virtually free groups

This page was built for publication: On finitely generated submonoids of virtually free groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317164)