首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 LF whether the subsemigroup generated by L is free and also whether it is almost-free.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号