We prove that the ranking problem for unambiguous context-free languages is NC1-reducible to the value problem for algebraic formal power series in noncommuting variables. In the particular case of regular languages we show that the problem of ranking is NC1-reducible to the problem of counting the number of strings of given length in suitable regular languages. As a consequence ranking problems for regular languages are NC1-reducible to integer division and hence computable by log-space uniform boolean circuits of polynomial size and depth O(log n log log n), or by P-uniform boolean circuits of polynomial size and depth O(log n).
Ranking and formal power series / A. Bertoni, D. Bruschi, M. Goldwurm. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 79:1(1991 Feb), pp. 25-35.
Ranking and formal power series
A. BertoniPrimo
;D. BruschiSecondo
;M. GoldwurmUltimo
1991
Abstract
We prove that the ranking problem for unambiguous context-free languages is NC1-reducible to the value problem for algebraic formal power series in noncommuting variables. In the particular case of regular languages we show that the problem of ranking is NC1-reducible to the problem of counting the number of strings of given length in suitable regular languages. As a consequence ranking problems for regular languages are NC1-reducible to integer division and hence computable by log-space uniform boolean circuits of polynomial size and depth O(log n log log n), or by P-uniform boolean circuits of polynomial size and depth O(log n).Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.