50 ans de problèmes de spectre en logique
More, Malika1
1 LAIC, Université d’Auvergne
Femmes & math, Femmes en informatique : les encourager de l’école à l’université (2006), pp. 5-8.
More, Malika 1

1 LAIC, Université d’Auvergne 
@article{RFM_2006__8_S1_5_0,
     author = {More, Malika},
     title = {50 ans de probl\`emes de spectre en logique},
     journal = {Femmes & math},
     pages = {5--8},
     publisher = {Association femmes et math\'ematiques},
     year = {2006},
     language = {fr},
     url = {http://www.numdam.org/item/RFM_2006__8_S1_5_0/}
}
TY  - JOUR
AU  - More, Malika
TI  - 50 ans de problèmes de spectre en logique
JO  - Femmes & math
PY  - 2006
SP  - 5
EP  - 8
PB  - Association femmes et mathématiques
UR  - http://www.numdam.org/item/RFM_2006__8_S1_5_0/
LA  - fr
ID  - RFM_2006__8_S1_5_0
ER  - 
%0 Journal Article
%A More, Malika
%T 50 ans de problèmes de spectre en logique
%J Femmes & math
%D 2006
%P 5-8
%I Association femmes et mathématiques
%U http://www.numdam.org/item/RFM_2006__8_S1_5_0/
%G fr
%F RFM_2006__8_S1_5_0
More, Malika. 50 ans de problèmes de spectre en logique. Femmes & math, Femmes en informatique : les encourager de l’école à l’université (2006), pp. 5-8. http://www.numdam.org/item/RFM_2006__8_S1_5_0/

[1] Günter Asser. Das Reprasentenproblem in Pradikatenkalkül der ersten Stufe mit Identitat. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 1 :252-263, 1955. | MR | Zbl

[2] Claude A. Christen. Spektralproblem und Komplexitütstheorie. PhD thesis, Eidgenossische Technische Hochschule (ETH), Zürich, Switzerland, 1974.

[3] Arnaud Durand, Ronald Fagin, and Bernd Loescher. Spectra with only unary fonction symbols. In Mogens Nielsen and Wolfgang Thomas, editors, Computer Science Logic, 11th International Workshop, CSL’97, Annual Conference of the EACSL, Aarhus, Denmark, August 23-29, 1997, Selected Papers, volume 1414 of Lecture Notes in Computer Science, pages 189-202. Springer, 1998. | MR | Zbl

[4] Arnaud Durand, Neil D. Jones, Johann Makowsky, and Malika More. Fifty years of the spectrum problem : survey and new results. En preparation. | Zbl

[5] Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In Richard M. Karp, editor, Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973), volume 7 of SIAM-AMS Proceedings, pages 43-73, Providence, R.I., 1974. American Mathematical Society. | MR | Zbl

[6] Ronald Fagin. A spectrum hierarchy. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 21 :123-134, 1975. | MR | Zbl

[7] Etienne Grandjean. Universal quantiers and time complexity of random access machines. Mathematical Systems Theory, 18(2) :171-187, 1985. | MR | Zbl

[8] Etienne Grandjean. First-order spectra with one variable. Journal of Computer and System Sciences, 40(2) :136-153, 1990. | MR | Zbl

[9] Aaron Hunter. Spectrum hierarchies and subdiagonal fonctions. In 18th International Symposium on Logic in Computer Science (LICS’03), pages 281-290. IEEE Press, 2003.

[10] Neil Immerman. Descriptive Complexity. Graduate Texts in Computer Science. Springer, 1999. | MR | Zbl

[11] Neil D. Jones and Alan L. Selman. Turing machines and the spectra of first-order formulas with equality. In Conference Record, Fourth Annual ACM Symposium on Theory of Computing, 1-3 May 1972, Denver, Colorado, USA, pages 157-167, New York, NY, USA, 1972. ACM Press. | Zbl

[12] Heinrich Scholz. Ein ungelostes Problem in der symbolischen Logik. Journal of Symbolic Logic, 17 :160, 1952.

[13] Boris A. Trakhtenbrot. Impossibility of an algorithm for the decision problem in nite classes. Doklady Akademii Nauk SSSR, 70 :569-572, 1950. | MR | Zbl