First order logic, fixed point logic and linear order

DOI10.1007/3-540-61377-3_37MaRDI QIDQ6560167zbMATHFDO

Authors Anuj Dawar, Steven Lindell, Scott Weinstein

Publication date 21 June 2024

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)

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

Cites work

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

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)