The role of rudimentary relations in complexity theory
Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 à Paris, Mémoires de la Société Mathématique de France, Série 2, no. 16 (1984), pp. 41-51.
@incollection{MSMF_1984_2_16__41_0,
     author = {Volger, Hugo},
     title = {The role of rudimentary relations in complexity theory},
     booktitle = {Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 \`a Paris},
     editor = {Delon, F. and Lascar, D. and Parigot, M. and Sabbagh, G.},
     series = {M\'emoires de la Soci\'et\'e Math\'ematique de France},
     pages = {41--51},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {16},
     year = {1984},
     doi = {10.24033/msmf.311},
     zbl = {0558.68043},
     mrnumber = {87b:03083},
     url = {archive.numdam.org/item/MSMF_1984_2_16__41_0/}
}
Volger, Hugo. The role of rudimentary relations in complexity theory, dans Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 à Paris, Mémoires de la Société Mathématique de France, Série 2, no. 16 (1984), pp. 41-51. doi : 10.24033/msmf.311. http://archive.numdam.org/item/MSMF_1984_2_16__41_0/

[1] Bennett, J.H.: On spectra, Ph. D. Thesis, Princeton Univ., Princeton N.J. 1962, 135 pp.

[2] Berman, L.: The complexity of logical theories, Theoret. Comp. Sci. 11 (1980), 71-77. | MR 82c:03061b | Zbl 0475.03017

[3] Book, R., Greibach, S.: Quasirealtime languages, Math. Systems Theory 4 (1970), 97-111. | MR 43 #1772 | Zbl 0188.33102

[4] Chandra, A.K., Stockmeyer, L.J.: Alternation, in : Proc. 17th IEEE Symp. Found. of Comp. Sci. (1976), 98-108. | MR 58 #25107

[5] Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation, J. ACM 28 (1981), 114-133. | MR 83g:68059 | Zbl 0473.68043

[6] Harrow, K.: The bounded arithmetic hierarchy, Information and Control 36 (1978), 102-117. | MR 57 #16010 | Zbl 0374.02019

[7] Jones, N.D.: Context-free languages and rudimentary attributes, Math. Systems Theory 3 (1969), 102-109, 11 (1977/1978), 379-380. | MR 41 #9671 | Zbl 0179.02202

[8] Jones, N.D.: Space-bounded reducibility among combinatorial problems, J. Comp. System Sci. 11 (1975), 68-85, 15 (1977), 241. | MR 53 #2020 | Zbl 0317.02039

[9] King, K.N., Wrathall, C.: Stack languages and log n space, J. Comp. System Sci. 17 (1978), 281-299. | MR 80h:68069 | Zbl 0388.68070

[10] Kozen, D.C.: On parallelism in Turing machines, in: Proc. 17th IEEE Symp. Found. of Comp. Sci. (1976), 89-97. | MR 57 #4621

[11] Meloul, J.: Rudimentary predicates, low level complexity classes and related automata, Ph. D. Thesis, Oxford Univ., Oxford 1979, 210 pp.

[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] Nepomnjascii, V.A.: Rudimentary predicates and Turing computations, Soviet Math. Dokl. 11 (1970), 1462-1465. | MR 43 #7326

[14] Nepomnjascii, V.A.: Rudimentary interpretation of two-tape Turing computations, Kibernetika (1970) 2, 29-35. | MR 52 #7879 | Zbl 0245.02034

[15] Nepomnjascii, V.A.: Examples of predicates not expressible by S-Rud formulae, Kibernetika (1978) 2, 44-46. | MR 81h:03083 | Zbl 0391.03017

[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. | Zbl 0521.68043

[17] Quine, W.V. : Concatenation as a basis for arithmetic, J. Symb. Logic 11 (1946), 105-114. | MR 8,307b | Zbl 0063.06362

[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. | MR 58 #179 | Zbl 0393.03028

[19] Smullyan, R.: Theory of formal systems, Annals of Math. Studies 47, Princeton Univ. Press 1961, 147 pp. | MR 22 #12042 | Zbl 0097.24503

[20] Stockmeyer, L.J.: The polynomial-time hierarchy, IBM Res. Report RC5379 (1975).

[21] Stockmeyer, L.J.: The polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1977), 1-22. | MR 55 #11716 | Zbl 0353.02024

[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. | MR 84m:68042 | Zbl 0538.03035

[23] Volger, H.: Rudimentary relations and Turing machines with linear alternation, to appear in: Proc. Conf. Recursive Combinatorics, Münster 1983, 6 pp. | Zbl 0558.68042

[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. | MR 82b:03085 | Zbl 0483.03024

[25] Wilkie, A.J.: On core structures for Peano arithmetic, in: Logic Coll. '80, North-Holland Publ. Comp. 1982, 311-314. | MR 84j:03142 | Zbl 0517.03030

[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. | MR 82k:03074 | Zbl 0499.03021

[27] Wrathall, C.: Subrecursive predicates and automata, Ph. D. Thesis, Harvard Univ., Cambridge Mass. 1975, 156 pp.

[28] Wrathall, C.: Complete sets and the polynomial-time hierarchy, Theoret. Comp. Sci. 3 (1977), 23-33. | MR 55 #11717 | Zbl 0366.02031

[29] Wrathall, C.: Rudimentary predicates and relative computation, SIAM J. Computing 7 (1978), 194-209. | MR 58 #3754 | Zbl 0375.68030

[30] Yu, Y.Y.: Rudimentary relations and formal languages, Ph. D. Thesis, Univ. of California, Berkeley Cal. 1970, 47 pp.

[31] Yu, Y.Y.: Rudimentary relations and stack languages, Math. Systems Theory 10 (1977), 337-343. | MR 58 #19399 | Zbl 0371.68022