First order logic, fixed point logic and linear order

DOI10.1007/3-540-61377-3_37zbMATH Open1540.03063MaRDI QIDQ6560167FDOQ6560167

Authors: Anuj Dawar, Steven Lindell, Scott Weinstein 

Publication date: 21 June 2024

Recommendations

• On the ordered conjecture
• Infinitary logic and inductive definability over finite structures
• Tameness in least fixed-point logic and McColm's conjecture
• On fixed-point logic with counting
• The expressive power of finitely many generalized quantifiers

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Logic in computer science (03B70) Other infinitary logic (03C75)

Cites Work

• Elementary induction on abstract structures
• On uniformity within \(NC^ 1\)
• Definability with bounded number of bound variables
• Datalog extensions for database queries and updates
• Computing with first-order logic
• Deux ou trois choses que je sais de L_n
• Relational queries computable in polynomial time
• The expressive power of finitely many generalized quantifiers
• Upper and lower bounds for first order expressibility
• Rudimentary Predicates and Relative Computation
• Infinitary logic and inductive definability over finite structures
• Infinitary logics and 0-1 laws
• Title not available (Why is that?)
• When is arithmetic possible?
• Title not available (Why is that?)

This page was built for publication: First order logic, fixed point logic and linear order

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