How to define a linear order on finite models

DOI10.1016/S0168-0072(97)00008-0zbMath0884.03034OpenAlexW2073354681MaRDI QIDQ1371431

Kerkko Luosto, Phokion G. Kolaitis, Lauri Hella

Publication date: 7 January 1998

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(97)00008-0

zbMATH Keywords

infinitary logiclinear orderfinite model theoryimplicit definabilityleast fixpoint logicrigid modelsfinite rigid structuresminimal order partial querypartial fixpoint logicRescher quantifier

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models with special properties (saturated, rigid, etc.) (03C50)

Related Items (5)

Finite Variable Logics in Descriptive Complexity Theory ⋮ The monadic second-order logic of graphs. X: Linear orderings ⋮ Descriptive complexity of graph spectra ⋮ Zero-one law and definability of linear order ⋮ Epimorphisms in cylindric algebras and definability in finite variable logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Definability with bounded number of bound variables
• When is arithmetic possible?
• On the expressive power of Datalog: tools and a case study.
• Fixed-point extensions of first-order logic
• Descriptive characterizations of computational complexity
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Model theory.
• Infinitary logics and 0-1 laws
• An optimal lower bound on the number of variables for graph identification
• Elementary induction on abstract structures
• Relative complexity of checking and evaluating
• The polynomial-time hierarchy
• The number of finite relational structures
• Logical hierarchies in PTIME
• Structure and complexity of relational queries
• Computing with first-order logic
• Infinitary logic and inductive definability over finite structures
• Almost Everywhere Equivalence of Logics in Finite Model Theory
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Complexity Measures for Public-Key Cryptosystems
• Second-order and Inductive Definability on Finite Structures
• Random Graph Isomorphism
• Probabilities on finite models
• On Moschovakis closure ordinals
• Implicit definability and infinitary logic in finite model theory
• Generalized Quantifiers and Logical Reducibilities
• The expressive power of fixed-point logic with counting
• On finite rigid structures

This page was built for publication: How to define a linear order on finite models