First-order spectra with one variable

DOI10.1016/0022-0000(90)90009-AzbMath0694.68034MaRDI QIDQ909462

Etienne Grandjean

Publication date: 1990

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

random access machinesuccessor structurefirst-order sentenceNRAM(cn)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (15)

Invariance properties of RAMs and linear time ⋮ One unary function says less than two in existential second order logic ⋮ A logical approach to locality in pictures languages ⋮ First-order spectra with one binary predicate ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Graph properties checkable in linear time in the number of vertices ⋮ On winning Ehrenfeucht games and monadic NP ⋮ On the Variable Hierarchy of First-Order Spectra ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Complexity of syntactical tree fragments of independence-friendly logic ⋮ Independence-friendly logic without Henkin quantification ⋮ Linear time and the power of one first-order universal quantifier ⋮ Regular Graphs and the Spectra of Two-Variable Logic with Counting ⋮ Unnamed Item ⋮ Investigation of binary spectra by explicit polynomial transformations of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Minimal coverings for incompletely specified sequential machines
• Number of quantifiers is better than number of tape cells
• Model theory
• Structure and complexity of relational queries
• Concerning a problem of H. Scholz
• The Spectra of First-Order Sentences and Computational Complexity
• Universal quantifiers and time complexity of random access machines
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• A Natural NP-Complete Problem with a Nontrivial Lower Bound
• Complexity classes and theories of finite models
• Monadic generalized spectra
• Turing machines and the spectra of first-order formulas

This page was built for publication: First-order spectra with one variable