On the rational subset problem for groups.
From MaRDI portal
finitely generated groupsdecidabilityfinite automataformal languagesgraphs of groupsword problemdecision problemsrational subset problemregular intersection decision problem
Formal languages and automata (68Q45) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Generators, relations, and presentations of groups (20F05) 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 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
Cites work
- 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?)
- FOLDINGS, GRAPHS OF GROUPS AND THE MEMBERSHIP PROBLEM
- FREE INVERSE MONOIDS AND GRAPH IMMERSIONS
- Finite and infinite cyclic extensions of free groups
- Finiteness Conditions on Subgroups and Formal Language Theory
- GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
- Groups assembled from free and direct products
- Groups, the theory of ends, and context-free languages
- 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
- \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata
Cited in
(41)- Rational subsets of groups
- Closure properties of knapsack semilinear groups
- Submonoids and rational subsets of groups with infinitely many ends.
- scientific article; zbMATH DE number 1438911 (Why is no real title available?)
- On the rational subsets of the free group
- scientific article; zbMATH DE number 6540722 (Why is no real title available?)
- On the decidability of semigroup freeness.
- Presburger arithmetic with stars, rational subsets of graph groups, and nested zero tests
- An automata theoretic approach to the generalized word problem in graphs of groups.
- The emptiness problem for valence automata over graph monoids
- Algebraic and context-free subsets of subgroups
- On the membership problem for finite automata over symmetric groups
- Tilings and submonoids of metabelian groups.
- scientific article; zbMATH DE number 3876579 (Why is no real title available?)
- MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES
- The submonoid and rational subset membership problems for graph groups.
- Bottom-up rewriting for words and terms
- scientific article; zbMATH DE number 4010764 (Why is no real title available?)
- Two problems for solvable and nilpotent groups
- On one-relator groups and units of special one-relation inverse monoids
- Word problems recognisable by deterministic blind monoid automata
- The rational subset membership problem for groups: a survey
- ON GROUPS AND COUNTER AUTOMATA
- Polycyclic and Bicyclic Valence Automata
- Partially commutative inverse monoids.
- New results on the prefix membership problem for one-relator groups
- scientific article; zbMATH DE number 1985667 (Why is no real title available?)
- On the rational subsets of the monogenic free inverse monoid
- Rational subsets of unitriangular groups.
- Formal Languages and Groups as Memory
- Knapsack problems in products of groups
- Separability of rational relations in \(A^* \times \mathbb N^m\) by recognizable relations is decidable
- Small overlap monoids. II: Automatic structures and normal forms.
- Algorithmic properties of inverse monoids with hyperbolic and tree-like Schützenberger graphs
- Semigroup automata with rational initial and terminal sets
- Rational subsets of polycyclic monoids and valence automata
- On the existence of universal rational structures for groups.
- RATIONAL SUBSETS IN HNN-EXTENSIONS AND AMALGAMATED PRODUCTS
- Rational cross-sections, bounded generation, and orders on groups
- Recent advances on reachability problems for valence systems (invited talk)
- Free group languages: Rational versus recognizable
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)
