Free and almost-free subsemigroups of a free semigroup

✍ Scribed by Ronald V. Book

• Publisher: Elsevier Science
• Year: 1973
• Tongue: English
• Weight: 381 KB
• Volume: 4
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(73)80004-4

✦ Synopsis

A subsemigroup S of a free semigroup F(Z) is almost-free if there is a free subsemigroup T such that S c T c F(2;) and TkS is finite. It is shown that it is decidable whether a subsemigroup generated by a regular subset of F(Z) is almost-free. Sufficient conditions are given such that if a family F of subsets ofF(Z) satisfies these conditions, then it is undecidable for L ~/: whether the subsemigroup generated by L is free and also whether it is almost-free.