The complexity of ranking

1 January 1988

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 204-212
https://doi.org/10.1109/sct.1988.5280

Abstract

It is shown that ranking languages accepted by one-way unambiguous auxiliary pushdown automata are in NC/sup (2)/. Negative results about ranking for several classes of simple languages are proved. It is shown that C is rankable in deterministic polynomial time if P= Hash P, where C is any of the following classes of languages: (1) languages accepted by logtime-bounded nondeterministic Turing machines; (2) languages accepted by (uniform) families of unbounded fan-in circuits of constant depth and polynomial size; (3) languages accepted by two-way deterministic finite automata; (4) languages accepted by multihead deterministic finite automata; (5) languages accepted by one-way nondeterministic logspace-bounded Turing machines; and (6) finitely ambiguous linear context-free languages.

Keywords

This publication has 0 references indexed in Scilit: