Free and almost-free subsemigroups of a free semigroup |
| |
Authors: | Ronald V Book |
| |
Institution: | Aiken Computation Laboratory, Harvard University, Cambridge, Mass. 02138, USA |
| |
Abstract: | A subsemigroup S of a free semigroup F(Σ) is almost-free if there is a free subsemigroupT such that S?T?F(Σ) and T/S is finite. It is shown that it is decidable whether a subsemigroup generated by a regular subset of F(Σ) is almost-free. Sufficient- conditions are given such that if a family F of subsets of F(Σ) satisfies these conditions, then it is undecidable for L∈F whether the subsemigroup generated by L is free and also whether it is almost-free. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|