Normalizable linear orders and generic computations in finite models

DOI10.1007/S001530050128MaRDI QIDQ1306793zbMATH OpenOpenAlexFDO

Authors 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

complexity classesfinite modelsDawar's conjecturefinitely axiomatizable class of rigid structuresgeneric queriesleast fixpoint logicnormalizability of linear orderStolboushkin'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) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• How to define a linear order on finite models
• On finite rigid structures
• On the ordered conjecture
• Infinitary logic and inductive definability over finite structures
• Computer Science Logic

Cited in

(2)

• Models of \textsf{ZFA} in which every linearly ordered set can be well ordered
• On finite rigid structures

This page was built for publication: Normalizable linear orders and generic computations in finite models

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