Rational subsets and submonoids of wreath products.

DOI10.1016/j.ic.2014.12.014zbMath1332.20038arXiv1302.2455OpenAlexW2261634751MaRDI QIDQ2347806

Markus Lohrey, Georg Zetzsche, Benjamin Steinberg

Publication date: 9 June 2015

Published in: Information and Computation, Automata, Languages, and Programming (Search for Journal in Brave)

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

zbMATH Keywords

decidabilitymembership problemfinitely generated monoidsrational subsets of groupsrational subsets of wreath products

Mathematics Subject Classification ID

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

Related Items

On the word problem for special monoids ⋮ Lamplighter groups and automata ⋮ Parallel Identity Testing for Skew Circuits with Big Powers and Applications ⋮ Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups ⋮ Two problems for solvable and nilpotent groups ⋮ Parallel identity testing for skew circuits with big powers and applications ⋮ Rational subsets and submonoids of wreath products. ⋮ Knapsack Problems for Wreath Products

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular languages and partial commutations
• Submonoids and rational subsets of groups with infinitely many ends.
• Tilings and submonoids of metabelian groups.
• Subgroup distortion in wreath products of cyclic groups.
• Logical aspects of Cayley-graphs: the group case
• On regularity of context-free languages
• On the rational subset problem for groups.
• The submonoid and rational subset membership problems for graph groups.
• Distortion of wreath products in some finitely presented groups.
• On total regulators generated by derivation relations
• The occurrence problem for extensions of Abelian groups by nilpotent groups
• Sequential grammars and automata with valences
• Verifying lossy channel systems has nonprimitive recursive complexity.
• Rational subsets and submonoids of wreath products.
• Rational sets in commutative monoids
• Regular solutions of language inequalities and well quasi-orders
• On the decidability of accessibility problems (extended abstract)
• SOLVABILITY OF EQUATIONS IN GRAPH GROUPS IS DECIDABLE
• Leftist Grammars Are Non-primitive Recursive
• Theories of HNN-Extensions and Amalgamated Products
• Formal Languages and Groups as Memory
• Post Embedding Problem Is Not Primitive Recursive, with Applications to Channel Systems
• On free monoids partially ordered by embedding
• Ordering by Divisibility in Abstract Algebras
• Well-structured transition systems everywhere!