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


On Bounded Rational Trace Languages
Authors:Christian Choffrut  Flavio D’Alessandro  Stefano Varricchio
Affiliation:1. Laboratoire LIAFA, Université de Paris 7, 2 pl. Jussieu, 75251, Paris Cedex 05, France
2. Dipartimento di Matematica, Università di Roma “La Sapienza”, Piazzale Aldo Moro 2, 00185, Rome, Italy
3. Dipartimento di Matematica, Università di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133, Rome, Italy
Abstract:In this paper, for a finitely generated monoid M, we tackle the following three questions:
  1. Is it possible to give a characterization of rational subsets of M which have polynomial growth?
  2. What is the structure of the counting function of rational sets which have polynomial growth?
  3. Is it true that every rational subset of M has either exponential growth or it has polynomial growth? Can one decide for a given rational set which of the two options holds?
We give a positive answer to all the previous questions in the case that M is a direct product of free monoids. Some of the proved results also extend to trace monoid.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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