A restricted second order logic for finite structures

DOI10.1007/3-540-60178-3_94OpenAlexW2178865018WikidataQ58215773 ScholiaQ58215773MaRDI QIDQ6064291

Anuj Dawar

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60178-3_94

zbMATH Keywords

linear orderorder logicrelation symbolorder formulasimultaneous induction

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fixed-point extensions of first-order logic
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Infinitary logics and 0-1 laws
• An optimal lower bound on the number of variables for graph identification
• Elementary induction on abstract structures
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• Infinitary logic and inductive definability over finite structures
• Inductive definitions over finite structures
• Properties of Almost All Graphs and Generalized Quantifiers
• Relational queries computable in polynomial time
• On Moschovakis closure ordinals
• Some Remarks on Generalized Spectra
• Fixpoint logics, relational machines, and computational complexity

This page was built for publication: A restricted second order logic for finite structures