On the rational subset problem for groups.

DOI10.1016/J.JALGEBRA.2006.05.020MaRDI QIDQ875109zbMATH OpenOpenAlexFDO

Authors Mark Kambites, Pedro V. Silva, Benjamin Steinberg

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

decidabilitydecision problemsfinite automatafinitely generated groupsformal languagesgraphs of groupsrational subset problemregular intersection decision problemword problem

Mathematics Subject Classification ID

Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) 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) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Abstract: We use language theory to study the rational subset problem for groups and monoids. We show that the decidability of this problem is preserved under graph of groups constructions with finite edge groups. In particular, it passes through free products amalgamated over finite subgroups and HNN extensions with finite associated subgroups. We provide a simple proof of a result of Grunschlag showing that the decidability of this problem is a virtual property. We prove further that the problem is decidable for a direct product of a group G with a monoid M if and only if membership is uniformly decidable for G-automata subsets of M. It follows that a direct product of a free group with any abelian group or commutative monoid has decidable rational subset membership.

Recommendations

• The submonoid and rational subset membership problems for graph groups.
• scientific article; zbMATH DE number 1820023
• The rational subset membership problem for groups: a survey

Cites work

• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
• Finite and infinite cyclic extensions of free groups
• Finiteness Conditions on Subgroups and Formal Language Theory
• FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
• FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
• Groups assembled from free and direct products
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Groups, the theory of ends, and context-free languages
• scientific article; zbMATH DE number 4049112 (Why is no real title available?)
• scientific article; zbMATH DE number 3660804 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3574107 (Why is no real title available?)
• scientific article; zbMATH DE number 2144687 (Why is no real title available?)
• scientific article; zbMATH DE number 1842475 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• scientific article; zbMATH DE number 848082 (Why is no real title available?)
• scientific article; zbMATH DE number 1421185 (Why is no real title available?)
• scientific article; zbMATH DE number 3238653 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3339488 (Why is no real title available?)
• scientific article; zbMATH DE number 2209675 (Why is no real title available?)
• scientific article; zbMATH DE number 3057909 (Why is no real title available?)
• Indexed Grammars—An Extension of Context-Free Grammars
• Inverse automata and profinite topologies on a free group
• Monadic Thue systems
• Nested Stack Automata
• On Context-Free Languages
• On groups whose word problem is solved by a counter automaton.
• On one-relator monoids and one-relator groups
• On the equivalence and containment problems for context-free languages
• Rational sets in commutative monoids
• The accessibility of finitely presented groups
• Theory of Cryptography
• Topology of finite graphs

Cited in

(46)

• Small overlap monoids. II: Automatic structures and normal forms.
• Rational subsets of polycyclic monoids and valence automata
• On the rational subsets of the free group
• Two problems for solvable and nilpotent groups
• Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs
• Closure properties of knapsack semilinear groups
• Rational subsets of groups
• Semigroup automata with rational initial and terminal sets
• On the existence of universal rational structures for groups.
• Word problems recognisable by deterministic blind monoid automata
• The emptiness problem for valence automata over graph monoids
• On the rational subsets of the monogenic free inverse monoid
• On the membership problem for finite automata over symmetric groups
• Recent advances on reachability problems for valence systems (invited talk)
• On the decidability of semigroup freeness.
• The rational subset membership problem for groups: a survey
• scientific article; zbMATH DE number 3876579 (Why is no real title available?)
• New results on the prefix membership problem for one-relator groups
• RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
• Polycyclic and Bicyclic Valence Automata
• ON GROUPS AND COUNTER AUTOMATA
• Formal Languages and Groups as Memory
• scientific article; zbMATH DE number 4010764 (Why is no real title available?)
• scientific article; zbMATH DE number 1163638 (Why is no real title available?)
• scientific article; zbMATH DE number 1985667 (Why is no real title available?)
• Free group languages: Rational versus recognizable
• scientific article; zbMATH DE number 1438911 (Why is no real title available?)
• An automata theoretic approach to the generalized word problem in graphs of groups.
• Rational subsets of unitriangular groups.
• MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
• scientific article; zbMATH DE number 6540722 (Why is no real title available?)
• On one-relator groups and units of special one-relation inverse monoids
• Submonoids and rational subsets of groups with infinitely many ends.
• Algebraic and context-free subsets of subgroups
• Tilings and submonoids of metabelian groups.
• Rational cross-sections, bounded generation, and orders on groups
• Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
• Membership problems in braid groups and Artin groups
• Membership problems in finite groups
• Effective equation solving, constraints, and growth in virtually abelian groups
• Membership problems in infinite groups
• Bottom-up rewriting for words and terms
• Separability of rational relations in A^* N^m by recognizable relations is decidable
• Knapsack problems in products of groups
• The submonoid and rational subset membership problems for graph groups.
• Partially commutative inverse monoids.

This page was built for publication: On the rational subset problem for groups.

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