zbMATH — the first resource for mathematics

Generalized first-order spectra and polynomial-time recognizable sets. (English) Zbl 0303.68035
Complexity of Comput., Proc. Symp. appl. Math., New York City 1973, 43-73 (1974).

68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
03C68 Other classical first-order model theory
03B10 Classical first-order logic
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
03D05 Automata and formal grammars in connection with logical questions