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


Decision problems for inverse monoids presented by a single sparse relator
Authors:Susan Hermiller  Steven Lindblad  John Meakin
Affiliation:1. Department of Mathematics, University of Nebraska, Lincoln, NE, 68588-0130, USA
2. Hewitt Associates LLC, 45 South 7th Street, Suite 2100, Minneapolis, MN, 55402, USA
Abstract:We study a class of inverse monoids of the form M=Inv 〈Xw=1〉, where the single relator w has a combinatorial property that we call sparse. For a sparse word w, we prove that the word problem for M is decidable. We also show that the set of words in (XX −1)* that represent the identity in M is a deterministic context free language, and that the set of geodesics in the Schützenberger graph of the identity of M is a regular language.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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