scientific article; zbMATH DE number 3876579
[For the entire collection see Zbl 0539.00015.] This article starts with the observation that if G is a finitely generated group such that the cardinality of any rational (i.e. regular) subset of G can be computed and such that for any two rational subsets R,S of G, \(R\subseteq S\) is decidable, then the word problem for G, the occurrence problem, and various other problems can be solved in a uniform way. An algorithm proposed by Charles Sims for computation in a free group is reformulated to solve the cardinality and inclusion problems for rational subsets of G when G is a monadic group, and an example indicates that the algorithm may be useful in other cases too. A similar treatment of monadic groups was given previously by \textit{R. V. Book} [Lect. Notes Comput. Sci. 138, 360-368 (1982; Zbl 0535.68011)].
- Thue systems as rewriting systems
- Complexity, combinatorial group theory and the language of palutators
- Computing presentations for subgroups of polycyclic groups and of context-free groups
- Gilman's conjecture
- Rewriting systems, plain groups, and geodetic graphs
- Rational subsets of groups
- On the decidability of semigroup freeness.
- scientific article; zbMATH DE number 4010764 (Why is no real title available?)
- Commutativity in groups presented by finite Church-Rosser Thue systems
- scientific article; zbMATH DE number 4003555 (Why is no real title available?)
- Groups and NTS languages
- Deciding if the angle is zero inside free groups
- Membership problems in infinite groups
- About the descriptive power of certain classes of finite string-rewriting systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3341886)