The ultra-weak Ash conjecture and some particular cases

DOI10.1002/MALQ.200510010MaRDI QIDQ3376535zbMATH OpenOpenAlexWikidataFDO

Authors Annie Chateau, Malika More

Publication date 24 March 2006

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200510010

zbMATH Keywords

descriptive complexityfinite modelsspectrum conjectureAsh's conjecture

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• A Conjecture Concerning the Spectrum of a Sentence
• On the asymptotic behavior of some counting functions, II
• scientific article; zbMATH DE number 2121574
• A note on first-order spectra with binary relations
• Counting unlabeled structures

Cites work

• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 1223621 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A spectrum hierarchy
• Complexity classes defined by counting quantifiers
• On languages with two variables

Cited in

(1)

• Fifty years of the spectrum problem: survey and new results

This page was built for publication: The ultra-weak Ash conjecture and some particular cases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3376535)