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.
|Titolo:||The complexity of computing the number of strings of given length in context-free languages|
BERTONI ALBERTO (Primo)
GOLDWURM MASSIMILIANO (Secondo)
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||1991|
|Digital Object Identifier (DOI):||10.1016/0304-3975(91)90023-U|
|Appare nelle tipologie:||01 - Articolo su periodico|