The role of rudimentary relations in complexity theory
Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 à Paris, Mémoire de la Société mathématique de France, Nouvelle série, 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\'emoire de la Soci\'et\'e math\'ematique de France},
     pages = {41--51},
     year = {1984},
     publisher = {Soci\'et\'e math\'ematique de France},
     number = {16},
     doi = {10.24033/msmf.311},
     mrnumber = {87b:03083},
     zbl = {0558.68043},
     url = {https://www.numdam.org/articles/10.24033/msmf.311/}
}
TY  - CHAP
AU  - Volger, Hugo
TI  - The role of rudimentary relations in complexity theory
BT  - Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 à Paris
AU  - Collectif
ED  - Delon, F.
ED  - Lascar, D.
ED  - Parigot, M.
ED  - Sabbagh, G.
T3  - Mémoire de la Société mathématique de France
PY  - 1984
SP  - 41
EP  - 51
IS  - 16
PB  - Société mathématique de France
UR  - https://www.numdam.org/articles/10.24033/msmf.311/
DO  - 10.24033/msmf.311
ID  - MSMF_1984_2_16__41_0
ER  - 
%0 Book Section
%A Volger, Hugo
%T The role of rudimentary relations in complexity theory
%B Compte-rendu de la table ronde de logique des 15 et 16 octobre 1983 à Paris
%A Collectif
%E Delon, F.
%E Lascar, D.
%E Parigot, M.
%E Sabbagh, G.
%S Mémoire de la Société mathématique de France
%D 1984
%P 41-51
%N 16
%I Société mathématique de France
%U https://www.numdam.org/articles/10.24033/msmf.311/
%R 10.24033/msmf.311
%F 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émoire de la Société mathématique de France, Nouvelle série, no. 16 (1984), pp. 41-51. doi: 10.24033/msmf.311

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

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

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

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

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

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

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

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

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

[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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :