On Parikh slender languages and power series

被引：12
作者：
Honkala, J
机构：
[1] Department of Mathematics, University of Turku
来源：
JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 1996年 / 52卷 / 01期
关键词：
D O I：
10.1006/jcss.1996.0014
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We define and study Parikh slender languages and power series. A language is Parikh slender if the number of words in the language with the same Parikh vector is bounded from above. As an application we get a new method for ambiguity proofs of context-free languages and a new proof of an earlier result of Autebert, Flajolet, and Gabarro concerning prefixes of infinite words. (C) 1996 Academic Press, Inc.
引用
收藏
页码：185 / 190
页数：6
相关论文
共 22 条
[1]   LANGUAGE-THEORETIC PROBLEMS ARISING FROM RICHELIEU CRYPTOSYSTEMS [J].
ANDRASIU, M ;
PAUN, G ;
DASSOW, J ;
SALOMAA, A .
THEORETICAL COMPUTER SCIENCE, 1993, 116 (02) :339-357
[2]   PREFIXES OF INFINITE WORDS AND AMBIGUOUS CONTEXT-FREE LANGUAGES [J].
AUTEBERT, JM ;
FLAJOLET, P ;
GABARRO, J .
INFORMATION PROCESSING LETTERS, 1987, 25 (04) :211-216
[3]  
Berstel J., 1988, RATIONAL SERIES THEI
[4]  
Bruyere V., 1994, Bull. Belgian Math. Soc., V1, P577, DOI [doi:10.36045/bbms/1103408547, DOI 10.36045/BBMS/1103408547]
[5]  
DASSOW J, 1993, EATCS B, V49, P152
[6]   RATIONAL SETS IN COMMUTATIVE MONOIDS [J].
EILENBERG, S ;
SCHUTZENBERGER, MP .
JOURNAL OF ALGEBRA, 1969, 13 (02) :173-+
[7]  
Eilenberg S., 1974, AUTOMATA LANGUAGES M, V59
[8]   ANALYTIC MODELS AND AMBIGUITY OF CONTEXT-FREE LANGUAGES [J].
FLAJOLET, P .
THEORETICAL COMPUTER SCIENCE, 1987, 49 (2-3) :283-309
[9]  
Ginsburg Seymour, 1966, The Mathematical Theory of Context Free Languages
[10]   ON A CONJECTURE ABOUT SLENDER CONTEXT-FREE LANGUAGES [J].
ILIE, L .
THEORETICAL COMPUTER SCIENCE, 1994, 132 (1-2) :427-434
123