This work presents an algebraic method, based on rational transductions, to study the sequential and parallel complexity of counting problems for regular and context-free languages. This approach allows us to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords, and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous context-free languages, the complexity of the value problem for rational and algebraic formal series in noncommuting variables, and a characterization of regular and Z-algebraic languages by means of ranking functions.
Rational transductions and complexity of counting problems / C. Choffrut, M. Goldwurm. - In: THEORY OF COMPUTING SYSTEMS. - ISSN 1432-4350. - 28:5(1995), pp. 437-450.
Rational transductions and complexity of counting problems
M. GoldwurmUltimo
1995
Abstract
This work presents an algebraic method, based on rational transductions, to study the sequential and parallel complexity of counting problems for regular and context-free languages. This approach allows us to obtain old and new results on the complexity of ranking and unranking as well as on other problems concerning the number of prefixes, suffixes, subwords, and factors of a word which belongs to a fixed language. Other results concern a suboptimal compression of finitely ambiguous context-free languages, the complexity of the value problem for rational and algebraic formal series in noncommuting variables, and a characterization of regular and Z-algebraic languages by means of ranking functions.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.