The complexity of ranking simple languages. (English) Zbl 0692.68059

Summary: Ranking is the problem of computing for an input string its lexicographic index in a given (fixed) language. This paper concerns the complexity of ranking. We show that ranking languages accepted by 1-way unambiguous auxiliary pushdown automata operating in polynomial time is in \(NC^{(2)}\). We also prove negative results about ranking for several classes of simple languages. C is rankable in deterministic polynomial time iff \(P=P^{\#P}\), where C is any of the following six 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 2-way deterministic pushdown automata, (4) languages accepted by multihead deterministic finite automata, (5) languages accepted by 1-way nondeterministic logspace-bounded Turing machines, and (6) finitely ambiguous linear context-free languages.


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
03D10 Turing machines and related notions
03D15 Complexity of computation (including implicit computational complexity)
Full Text: DOI


[1] Allender, E.: Invertible Functions, Ph.D. Thesis, Georgia Institute of Technology, 1985.
[2] Bertoni, A., Goldwurm, M., and Sabadini, N.: Computing the Counting Function of Context-Free Languages,Proc. 4th Symposium on Theoretical Aspects of Computer Science, LNCS 247, pp. 169–179, 1987. · Zbl 0634.68069
[3] Brandenburg, F.-J.: On One-Way Auxiliary Pushdown Automata,Proc. 3rd GI Conference on Theoretical Computer Science, LNCS 48, pp. 131–144, 1977. · Zbl 0359.68055
[4] Buss, S.: The Boolean Formula Value Problem Is in ALOGTIME,Proc. 19th ACM Symposium on Theory of Computing, pp. 123–131, 1987.
[5] Chandra, A., Kozen, D., and Stockmeyer, L.: Alternation,J. Assoc. Comput. Mach.,28, pp. 114–133, 1981. · Zbl 0473.68043
[6] Chang, J. H., Ibarra, O. H., Palis, M. A., and Ravikumar, B.: On Pebble Automata,Theoret. Computer Sci.,44, pp. 111–121, 1986. · Zbl 0612.68045
[7] Cook, S.: Path Systems and Language Recognition,Proc. 2nd ACM Symposium on Theory of Computing, pp. 70–72, 1970.
[8] Cook, S.: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers,J. Assoc. Comput. Mach.,18, pp. 4–18, 1971. · Zbl 0222.02035
[9] Cook, S.: A Taxonomy of Problems with Fast Parallel Algorithms,Inform. and Control,64, pp. 2–22, 1985. · Zbl 0575.68045
[10] Fortune, S., and Wyllie, J.: Parallelism in Random Access Machines,Proc. 10th ACM Symposium on Theory of Computing, pp. 114–118, 1978. · Zbl 1282.68104
[11] Ginsburg, S., and Spanier, E.: Finite-Turn Pushdown Automata,SIAM J. Control Optim.,4, pp. 429–453, 1966. · Zbl 0147.25302
[12] Goldberg, A., and Sipser, M.: Compression and Ranking,Proc. 17th ACM Symposium on Theory of Computing, pp. 440–448, 1985.
[13] Gurari, E., and Ibarra, O.: Path Systems: Constructions, Solutions, and Applications,SIAM J. Comput.,9, pp. 348–374, 1980. · Zbl 0447.68049
[14] Hartmanis, J.: Context-Free Languages and Turing Machine Computations,Proc. Symposium on Applied Mathematics, pp. 42–51, 1967. · Zbl 0189.29101
[15] Hemachandra, L.: On Ranking,Proc. 2nd Annual Conference on Structure in Complexity Theory, pp. 103–117, 1987.
[16] Hopcroft, J., and Ullman, J.:Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, MA, 1979. · Zbl 0426.68001
[17] Ruzzo, W.: Tree-Size Bounded Alternation,J. Comput. System Sci.,21, pp. 218–235, 1980. · Zbl 0445.68034
[18] Ruzzo, W.: On Uniform Circuit Complexity,J. Comput. System Sci.,22, pp. 365–383, 1981. · Zbl 0462.68013
[19] Sipser, M.: Borel Sets and Circuits Complexity,Proc. 15th ACM Symposium on Theory of Computing, pp. 61–69, 1983.
[20] Stockmeyer, L., and Vishkin, U.: Simulation of Random Access Machines by Circuits,SIAM J. Comput.,13, pp. 409–422, 1984. · Zbl 0533.68048
[21] Sudborough, I.: Relating Open Problems on the Tape Complexity of Context-Free Languages and Path Systems Problems,Proc. 12th Annual Johns Hopkins Conference on Information Sciences and Systems, pp. 329–335, 1978.
[22] Valiant, L.: The Complexity of Computing the Permanent,Theoret. Comput. Sci.,8, pp. 189–201, 1979. · Zbl 0415.68008
[23] Yao, A.: Separating the Polynomial-Time Hierarchy by Oracles,Proc. 26th IEEE Symposium on Foundations of Computer Science, pp. 1–10, 1985.
[24] Yao, A., and Rivest, R.:k+1 Heads Are Better thank, J. Assoc. Comput. Mach.,25, pp. 337–340, 1978. · Zbl 0372.68017
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.