On the rational subset problem for groups.

DOI10.1016/j.jalgebra.2006.05.020zbMath1123.20047arXivmath/0602454OpenAlexW2161913867MaRDI QIDQ875109

Mark Kambites, Benjamin Steinberg, Pedro V. Silva

Publication date: 11 April 2007

Published in: Journal of Algebra (Search for Journal in Brave)

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

zbMATH Keywords

decision problemsfinitely generated groupsword problemdecidabilityfinite automatagraphs of groupsformal languagesrational subset problemregular intersection decision problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

On the decidability of semigroup freeness, The emptiness problem for valence automata over graph monoids, Submonoids and rational subsets of groups with infinitely many ends., RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS, Algebraic and context-free subsets of subgroups, Knapsack problems in products of groups, On the membership problem for finite automata over symmetric groups, Tilings and submonoids of metabelian groups., Recent advances on reachability problems for valence systems (invited talk), Polycyclic and Bicyclic Valence Automata, Closure properties of knapsack semilinear groups, The submonoid and rational subset membership problems for graph groups., Partially commutative inverse monoids., Semigroup automata with rational initial and terminal sets, An automata theoretic approach to the generalized word problem in graphs of groups, ON GROUPS AND COUNTER AUTOMATA, Two problems for solvable and nilpotent groups, Formal Languages and Groups as Memory, Bottom-up rewriting for words and terms, New results on the prefix membership problem for one-relator groups, Small overlap monoids. II: Automatic structures and normal forms., Rational subsets of polycyclic monoids and valence automata, Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs, Rational subsets of unitriangular groups, Rational subsets and submonoids of wreath products., On one-relator groups and units of special one-relation inverse monoids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On groups whose word problem is solved by a counter automaton.
• Groups assembled from free and direct products
• Groups, the theory of ends, and context-free languages
• Topology of finite graphs
• The accessibility of finitely presented groups
• Monadic Thue systems
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• Rational sets in commutative monoids
• Finiteness Conditions on Subgroups and Formal Language Theory
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• Finite and infinite cyclic extensions of free groups
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• On Context-Free Languages
• Indexed Grammars—An Extension of Context-Free Grammars
• On the equivalence and containment problems for context-free languages
• Nested Stack Automata
• Theory of Cryptography
• On one-relator monoids and one-relator groups
• Inverse automata and profinite topologies on a free group