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. Bertoni
Primo
;
D. Bruschi
Secondo
;
M. Goldwurm
Ultimo
1991-02

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).
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/178303
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 5
social impact