Open AccessOn Bounded Rational Trace Languages
Author(s) -
Christian Choffrut,
Flavio D’Alessandro,
Stefano Varricchio
Publication year - 2008
Publication title -
theory of computing systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.479
H-Index - 44
eISSN - 1433-0490
pISSN - 1432-4350
DOI - 10.1007/s00224-008-9143-9
Subject(s) - monoid , trace (psycholinguistics) , free monoid , bounded function , product (mathematics) , mathematics , finitely generated abelian group , free product , algebra over a field , computer science , pure mathematics , linguistics , philosophy , chemistry , group (periodic table) , geometry , organic chemistry , mathematical analysis
In this paper, for a finitely generated monoid M, we tackle the following three questions: center dot Is it possible to give a characterization of rational subsets of M which have polynomial growth? center dot What is the structure of the counting function of rational sets which have polynomial growth? center dot 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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom