Turing machines and the spectra of first-order formulas
From MaRDI portal
Publication:4775859
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
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
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
