Arity and alternation in second-order logic

DOI10.1016/0168-0072(95)00013-5zbMath0854.03006OpenAlexW2007091370MaRDI QIDQ1919768

Y. B. Pnueli, Johann A. Makowsky

Publication date: 30 October 1996

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

Full work available at URL: https://doi.org/10.1016/0168-0072(95)00013-5

zbMATH Keywords

complexityalternations of quantifiersexpressiveness of second-order logic over finite structureshierarchies of second-order formulas

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (12)

Arity and alternation: a proper hierarchy in higher order logics ⋮ Truth definitions in finite models ⋮ On spectra of sentences of monadic second order logic with counting ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Tree-width and the monadic quantifier hierarchy. ⋮ Model-checking hierarchical structures ⋮ Unnamed Item ⋮ Second-order propositional modal logic and monadic alternation hierarchies ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ Data exchange and schema mappings in open and closed worlds ⋮ The monadic quantifier alternation hierarchy over grids and graphs ⋮ The closure of monadic NP

Uses Software

• AUTO

Cites Work

• On the definability of properties of finite graphs
• Classifying regular events in symbolic logic
• A regular characterization of graph languages definable in monadic second-order logic
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Reachability is harder for directed than for undirected finite graphs
• Second-order and Inductive Definability on Finite Structures
• Complexity classes and theories of finite models
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Arity and alternation in second-order logic