Normalizable linear orders and generic computations in finite models

DOI10.1007/s001530050128zbMath0933.03040OpenAlexW2010125230MaRDI QIDQ1306793

Alexei P. Stolboushkin, Michael A. Taitslin

Publication date: 5 October 1999

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s001530050128

zbMATH Keywords

finite modelscomplexity classesDawar's conjecturefinitely axiomatizable class of rigid structuresgeneric queriesleast fixpoint logicnormalizability of linear orderStolboushkin's conjecture

Mathematics Subject Classification ID

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