On the Variable Hierarchy of First-Order Spectra

DOI10.1145/2733376zbMath1354.03040arXiv1403.2225OpenAlexW2146314802MaRDI QIDQ2957699

Tony Tan, Eryk Kopczyński

Publication date: 27 January 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.2225

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07)

Related Items (1)

Unnamed Item

Cites Work

• Graph properties checkable in linear time in the number of vertices
• Finite-model theory -- A personal perspective
• Strong computational lower bounds via parameterized complexity
• First-order spectra with one variable
• A hierarchy for nondeterministic time complexity
• The Spectra of First-Order Sentences and Computational Complexity
• Linear FPT reductions and computational lower bounds
• Universal quantifiers and time complexity of random access machines
• Complexity classes and theories of finite models
• Turing machines and the spectra of first-order formulas
• Fifty years of the spectrum problem: survey and new results
• Computational Complexity
• On the complexity of \(k\)-SAT
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the Variable Hierarchy of First-Order Spectra