On some languages in NC

1. Allender, E., P-uniform circuit complexity, Tech. Report, Department of Comp. Science, The Rutgers University, DCS-TR-198.

   Google Scholar 

2. Alt, H., Eine untere Schranke fur den Platzbedarf bei der Analyse beschrankter kontextfreier Sprachen, Dissertation, Saarbrucken, (1976).

   Google Scholar 

3. Alt, H., Lower bounds on space complexity for context-free recognition, Acta Informatica 12, (1979), pp. 33–61.

   Article  MATH  MathSciNet  Google Scholar 

4. Barrington, D., Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proc. 18th Annual Symp. on Theory of Computing (1986), pp. 1–5

   Google Scholar 

5. Buss, S., Boolean formula-value problem is in ALOGTIME, Proc. of 19th Annual Symp. on Theory of Computing (1987), pp. 123–131.

   Google Scholar 

6. Chandra, A., D. Kozen, and L. Stockmeyer, Alternation, J. ACM 28, 1 (1981), pp. 114–133.

   Article  MATH  MathSciNet  Google Scholar 

7. Chang, J., O. Ibarra, M. Palis, and B. Ravikumar, On pebble automata, TCS 44 (1986), pp. 111–121.

   Article  MATH  MathSciNet  Google Scholar 

8. Cook, S., A taxonomy of problems with fast parallel algorithms, Information and Control 64 (1985), pp. 2–22.

   Article  MATH  MathSciNet  Google Scholar 

9. Harrison, M. and O. Ibarra, Multitape and multihead pushdown automata, Information and Control 13 (1968), pp. 433–470.

   Article  MATH  MathSciNet  Google Scholar 

10. Harrison, M., Introduction to Formal Language Theory, Addison-Wesley (1978).

    Google Scholar 

11. Hopcroft, J. and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley (1979).

    Google Scholar 

12. Ibarra, O. and C. Kim, A useful device for showing the solvability of some decision problems, JCSS 13 (1976), pp. 153–160.

    MATH  MathSciNet  Google Scholar 

13. Ibarra, O., Reversal-bounded multicounter machines and their decision problems, JACM 25 (1978), pp. 116–133.

    Article  MATH  MathSciNet  Google Scholar 

14. Ladner, R., R. Lipton, and L. Stockmeyer, Alternating pushdown and stack automata, SICOMP 13 (1984), pp. 135–155.

    MATH  MathSciNet  Google Scholar 

15. Lewis, P., J. Hartmanis, and R. Stearns, Memory bounds for the recognition of context-free and context-sensitive languages, IEEE Conf. Record on Switching Circuit Theory and Logical Design, pp. 191–202.

    Google Scholar 

16. Litow, B., On efficient deterministic simulation of Turing machine computations below logspace, MST 18 (1985), pp. 11–18.

    MATH  MathSciNet  Google Scholar 

17. Lynch, N., Log space recognition and translation of parenthesis languages, JACM 24 (1977), pp. 583–590.

    Article  MATH  MathSciNet  Google Scholar 

18. Monien, B. and I. Sudborough, On eliminating nondeterminism from Turing machines which use less than logarithm worktape space, TCS 21 (1982), pp. 237–253.

    Article  MATH  MathSciNet  Google Scholar 

19. Pippenger, N., On simultaneous resource bounds, Twentieth IEEE Foundations of Computer Science (1979) pp. 307–310.

    Google Scholar 

20. Ruzzo, W., On uniform circuit complexity, JCSS 22 (1981), pp. 365–383.

    MATH  MathSciNet  Google Scholar 

21. Savitch, W., Relationships between nondeterministic and deterministic tape complexities, JCSS 4 (1970), pp. 177–192.

    MATH  MathSciNet  Google Scholar 

22. Springsteel, F. and R. Ritchie, Language recognition by marking automata, Information and Control 4 (1972), pp. 313–330.

    MathSciNet  Google Scholar 

23. Sudborough, I., Tape-bounded complexity classes and multihead finite automata, JCSS 10 (1975), pp. 62–76.

    MATH  MathSciNet  Google Scholar 

24. Tompa, M., An extension of Savitch's theorem to small space bounds, IPL 12, 2 (1981), pp. 106–108.

    Article  MATH  MathSciNet  Google Scholar 

Download references