A characterization of poly-slender context-free languages

被引：22

作者：

Ilie, L ^{[1
]}

Rozenberg, G

Salomaa, A

机构：

[1] TUCS, Turku Ctr Comp Sci, Turku 20520, Finland

[2] Leiden Univ, Dept Comp Sci, NL-2300 RA Leiden, Netherlands

[3] Univ Colorado, Dept Comp Sci, Boulder, CO 80309 USA

来源：

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 2000年 / 34卷 / 01期

关键词：

context-free language; poly-slender language; Dyck loop;

D O I：

10.1051/ita:2000100

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

For a non-negative integer k, we say that a language L is k-poly-slender if the number of words of length n in L is of order O(n(k)). We give a precise characterization of the k-poly-slender context-free languages. The well-known characterization of the k-poly-slender regular languages is an immediate consequence of ours.

引用

页码：77 / 86

页数：10

共 20 条

[1] LANGUAGE-THEORETIC PROBLEMS ARISING FROM RICHELIEU CRYPTOSYSTEMS [J].