Computations with rational subsets of confluent groups.

*(English)*Zbl 0549.68025
EUROSAM 84, Symbolic and algebraic computation, Proc. int. Symp., Cambridge/Engl. 1984, Lect. Notes Comput. Sci. 174, 207-212 (1984).

[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 R. V. Book [Lect. Notes Comput. Sci. 138, 360-368 (1982; Zbl 0535.68011)].

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 R. V. Book [Lect. Notes Comput. Sci. 138, 360-368 (1982; Zbl 0535.68011)].

##### MSC:

68W30 | Symbolic computation and algebraic computation |

20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |

68Q45 | Formal languages and automata |