A restricted second order logic for finite structures

DOI10.1006/inco.1998.2703zbMath0909.68078OpenAlexW1980103601WikidataQ58215736 ScholiaQ58215736MaRDI QIDQ1271559

Anuj Dawar

Publication date: 10 November 1998

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1998.2703

zbMATH Keywords

finite model theory

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (18)

On symmetric circuits and fixed-point logics ⋮ Generalising automaticity to modal properties of finite structures ⋮ Semantic Restrictions over Second-Order Logic ⋮ Unnamed Item ⋮ The language of plain SO-tgds: composition, inversion and structural properties ⋮ SO F : A Semantic Restriction over Second-Order Logic and Its Polynomial-Time Hierarchy ⋮ On the Descriptive Complexity of Linear Algebra ⋮ Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs ⋮ The expressive power of \(k\)-ary exclusion logic ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ Affine systems of equations and counting infinitary logic ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ The Expressive Power of k-ary Exclusion Logic ⋮ Expressive power and complexity of partial models for disjunctive deductive databases ⋮ Arity hierarchies ⋮ The Relational Polynomial-Time Hierarchy and Second-Order Logic ⋮ Schema Mappings: A Case of Logical Dynamics in Database Theory ⋮ On the expressive power of monadic least fixed point logic

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
• Computing with first-order logic
• Infinitary logic and inductive definability over finite structures
• Inductive definitions over finite structures
• Relational queries computable in polynomial time
• Second-order and Inductive Definability on Finite Structures
• 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