On Bounded Rational Trace Languages

被引：4

作者：

Choffrut, Christian ^{[2
]}

D'Alessandro, Flavio ^{[1
]}

Varricchio, Stefano ^{[3
]}

机构：

[1] Univ Roma La Sapienza, Dipartimento Matemat, I-00185 Rome, Italy

[2] Univ Paris 07, Lab LIAFA, F-75251 Paris 05, France

[3] Univ Roma Tor Vergata, Dipartimento Matemat, I-00133 Rome, Italy

来源：

THEORY OF COMPUTING SYSTEMS | 2010年 / 46卷 / 02期

关键词：

Trace languages; Bounded languages; Rational relations; CONTEXT-FREE LANGUAGES; COMMUTATIVE MONOIDS; SERIES;

D O I：

10.1007/s00224-008-9143-9

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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.

引用

页码：351 / 369

页数：19

共 15 条

[1]

[Anonymous], 1979, Transductions and context-free languages

[2] Interpolated denumerants and Lambert series [J].

Bell, ET .

AMERICAN JOURNAL OF MATHEMATICS, 1943, 65 :382-386

[3]

BERTONI A, 1988, B EATCS, V35, P106

[4]

Bouillard A, 2003, LECT NOTES COMPUT SC, V2710, P159

[5] On the separability of sparse context-free languages and of bounded rational relations [J].

Choffrut, Christian ;

D'Alessandro, Flavio ;

Varricchio, Stefano .

THEORETICAL COMPUTER SCIENCE, 2007, 381 (1-3) :274-279

[6] On the structure of the counting function of sparse context-free languages [J].

D'Alessandro, F ;

Intrigila, B ;

Varricchio, S .

THEORETICAL COMPUTER SCIENCE, 2006, 356 (1-2) :104-117

[7]

de Luca A., 1999, FINITENESS REGULARIT

[8]

DIEKERT V, 1994, BOOK TRACES

[9]

DUBOC C, 1986, LECT NOTES COMPUT SC, V210, P192

[10] RATIONAL SETS IN COMMUTATIVE MONOIDS [J].

EILENBERG, S ;

SCHUTZENBERGER, MP .

JOURNAL OF ALGEBRA, 1969, 13 (02) :173-+

← 1 2 →