Turing machines and the spectra of first-order formulas

DOI10.2307/2272354zbMath0288.02021OpenAlexW2082778556WikidataQ56522038 ScholiaQ56522038MaRDI QIDQ4775859

Selman, Alan L., Neil D. Jones

Publication date: 1974

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2272354

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10)

Related Items (33)

Universal quantifiers and time complexity of random access machines ⋮ LOGICALITY AND MODEL CLASSES ⋮ Listing graphs that satisfy first-order sentences ⋮ Disturbing arithmetic ⋮ Some remarks on real numbers induced by first-order spectra ⋮ First-order spectra with one binary predicate ⋮ Applying, extending, and specializing pseudorecursiveness ⋮ Descriptive characterizations of computational complexity ⋮ Nondeterministic stack register machines ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ Computation models and function algebras ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Classifying the computational complexity of problems ⋮ First-order spectra with one variable ⋮ Complexity results for classes of quantificational formulas ⋮ Computing on structures ⋮ Fifty years of the spectrum problem: survey and new results ⋮ The quantifier structure of sentences that characterize nondeterministic time complexity ⋮ Finite-model theory -- A personal perspective ⋮ Inclusion complete tally languages and the Hartmanis-Berman conjecture ⋮ P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP ⋮ On Horn spectra ⋮ Axiomatizing Rectangular Grids with no Extra Non-unary Relations ⋮ Characterizations of periods of multi-dimensional shifts ⋮ European Summer Meeting of the Association for Symbolic Logic ⋮ Complexity classes and theories of finite models ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Hereditarily-finite sets, data bases and polynomial-time computability ⋮ Unnamed Item ⋮ Asymptotic invariants, complexity of groups and related problems ⋮ Lower bound results on lengths of second-order formulas ⋮ Some thoughts on computational models: from massive human computing to abstract state machines, and beyond ⋮ Complete problems in the first-order predicate calculus

Cites Work

• Writing pushdown acceptors
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Concerning a problem of H. Scholz
• Classes of languages and linear-bounded automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Turing machines and the spectra of first-order formulas