The role of rudimentary relations in complexity theory

 Access to full text

 Full (PDF)

1. [1] Bennett, J.H.: On spectra, Ph. D. Thesis, Princeton Univ., Princeton N.J. 1962, 135 pp. 
2. [2] Berman, L.: The complexity of logical theories, Theoret. Comp. Sci. 11 (1980), 71-77. Zbl0475.03017MR82c:03061b
3. [3] Book, R., Greibach, S.: Quasirealtime languages, Math. Systems Theory 4 (1970), 97-111. Zbl0188.33102MR43 #1772
4. [4] Chandra, A.K., Stockmeyer, L.J.: Alternation, in : Proc. 17th IEEE Symp. Found. of Comp. Sci. (1976), 98-108. Zbl0473.68043MR58 #25107
5. [5] Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation, J. ACM 28 (1981), 114-133. Zbl0473.68043MR83g:68059
6. [6] Harrow, K.: The bounded arithmetic hierarchy, Information and Control 36 (1978), 102-117. Zbl0374.02019MR57 #16010
7. [7] Jones, N.D.: Context-free languages and rudimentary attributes, Math. Systems Theory 3 (1969), 102-109, 11 (1977/1978), 379-380. Zbl0179.02202MR41 #9671
8. [8] Jones, N.D.: Space-bounded reducibility among combinatorial problems, J. Comp. System Sci. 11 (1975), 68-85, 15 (1977), 241. Zbl0317.02039MR53 #2020
9. [9] King, K.N., Wrathall, C.: Stack languages and log n space, J. Comp. System Sci. 17 (1978), 281-299. Zbl0388.68070MR80h:68069
10. [10] Kozen, D.C.: On parallelism in Turing machines, in: Proc. 17th IEEE Symp. Found. of Comp. Sci. (1976), 89-97. MR57 #4621
11. [11] Meloul, J.: Rudimentary predicates, low level complexity classes and related automata, Ph. D. Thesis, Oxford Univ., Oxford 1979, 210 pp. 
12. [12] Meyer, A.R., Stockmeyer, L.J.: The equivalence problem for regular expressions with squaring requires exponential space, in : Proc. 13th IEEE Symp. Switching and Automata Theory (1972), 125-129. 
13. [13] Nepomnjascii, V.A.: Rudimentary predicates and Turing computations, Soviet Math. Dokl. 11 (1970), 1462-1465. Zbl0223.02031MR43 #7326
14. [14] Nepomnjascii, V.A.: Rudimentary interpretation of two-tape Turing computations, Kibernetika (1970) 2, 29-35. Zbl0245.02034MR52 #7879
15. [15] Nepomnjascii, V.A.: Examples of predicates not expressible by S-Rud formulae, Kibernetika (1978) 2, 44-46. Zbl0391.03017MR81h:03083
16. [16] Orponen, P.: Complexity classes of alternating machines with oracles, in: Proc. 10th Coll. Automata, Languages and Programming (1983), Lecture Notes in Comp. Sci. 154, Springer Verlag 1983, 573-584. Zbl0521.68043
17. [17] Quine, W.V. : Concatenation as a basis for arithmetic, J. Symb. Logic 11 (1946), 105-114. Zbl0063.06362MR8,307b
18. [18] Simon, J.: Polynomially bounded quantification over higher types and a new hierarchy of the elementary sets, in: Non-classical Logic, Model Theory and Computability, North-Holland Publ. Comp. 1977, 267-281. Zbl0393.03028MR58 #179
19. [19] Smullyan, R.: Theory of formal systems, Annals of Math. Studies 47, Princeton Univ. Press 1961, 147 pp. Zbl0097.24503MR22 #12042
20. [20] Stockmeyer, L.J.: The polynomial-time hierarchy, IBM Res. Report RC5379 (1975). 
21. [21] Stockmeyer, L.J.: The polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1977), 1-22. Zbl0353.02024MR55 #11716
22. [22] Volger, H.: Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories, Theoret. Comp. Sci. 23 (1983), 333-338. Zbl0538.03035MR84m:68042
23. [23] Volger, H.: Rudimentary relations and Turing machines with linear alternation, to appear in: Proc. Conf. Recursive Combinatorics, Münster 1983, 6 pp. Zbl0558.68042
24. [24] Wilkie, A.J.: Applications of complexity theory to ∑0-definability problems in arithmetic, in: Model Theory of Algebra and Arithmetic, Lecture Notes in Math. 834, Springer Verlag 1980, 363-369. Zbl0483.03024MR82b:03085
25. [25] Wilkie, A.J.: On core structures for Peano arithmetic, in: Logic Coll. '80, North-Holland Publ. Comp. 1982, 311-314. Zbl0517.03030MR84j:03142
26. [26] Wilkie, A.J., Paris, J.B.: Models of arithmetic and the rudimentary sets, Bull. Math. Soc. Belg. Sér. B 33 (1981), 157-169. Zbl0499.03021MR82k:03074
27. [27] Wrathall, C.: Subrecursive predicates and automata, Ph. D. Thesis, Harvard Univ., Cambridge Mass. 1975, 156 pp. 
28. [28] Wrathall, C.: Complete sets and the polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1977), 23-33. Zbl0366.02031MR55 #11717
29. [29] Wrathall, C.: Rudimentary predicates and relative computation, SIAM J. Computing 7 (1978), 194-209. Zbl0375.68030MR58 #3754
30. [30] Yu, Y.Y.: Rudimentary relations and formal languages, Ph. D. Thesis, Univ. of California, Berkeley Cal. 1970, 47 pp. 
31. [31] Yu, Y.Y.: Rudimentary relations and stack languages, Math. Systems Theory 10 (1977), 337-343. Zbl0371.68022MR58 #19399