Computing the number of strings of given length contained in a language is related to classical problems of combinatorics, formal languages and computational complexity. Here we study the complexity of this problem in the case of context-free languages. It is shown that, for unambiguous context-free languages such a computation is "easy" and can be carried out by efficient parallel algorithms. On the contrary, for some context-free languages of ambiguity degree two, the problem becomes intractable. These results are related to other classical subjects concerning counting problems, exponential time recognizable languages and sparse sets.
The complexity of computing the number of strings of given length in context-free languages / A. Bertoni, M. Goldwurm, N. Sabadini. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 86:2(1991), pp. 325-342.
The complexity of computing the number of strings of given length in context-free languages
A. BertoniPrimo
;M. GoldwurmSecondo
;
1991
Abstract
Computing the number of strings of given length contained in a language is related to classical problems of combinatorics, formal languages and computational complexity. Here we study the complexity of this problem in the case of context-free languages. It is shown that, for unambiguous context-free languages such a computation is "easy" and can be carried out by efficient parallel algorithms. On the contrary, for some context-free languages of ambiguity degree two, the problem becomes intractable. These results are related to other classical subjects concerning counting problems, exponential time recognizable languages and sparse sets.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.