Gaifman normal forms for counting extensions of first-order logic
From MaRDI portal
finite model theoryfixed-parameter-tractable model checkingGaifman localitymodulo-counting quantifiers
Basic properties of first-order languages and structures (03C07) Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Parameterized complexity, tractability and kernelization (68Q27) Specification and verification (program logics, model checking, etc.) (68Q60)
Recommendations
- Hanf normal form for first-order logic with unary counting quantifiers
- First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
- An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
- The expressive power of fixed-point logic with counting
- On fixed-point logic with counting
Cites work
- Algorithmic uses of the Feferman-Vaught theorem
- An optimal construction of Hanf sentences
- An Optimal Gaifman Normal Form Construction for Structures of Bounded Degree
- Counting modulo quantifiers on finite structures
- Deciding first-order properties of locally tree-decomposable structures
- Easy problems for tree-decomposable graphs
- Elements of finite model theory.
- Generalized finite automata theory with an application to a decision problem of second-order logic
- Hanf normal form for first-order logic with unary counting quantifiers
- scientific article; zbMATH DE number 3819693 (Why is no real title available?)
- scientific article; zbMATH DE number 618821 (Why is no real title available?)
- scientific article; zbMATH DE number 803291 (Why is no real title available?)
- scientific article; zbMATH DE number 969067 (Why is no real title available?)
- Logic, graphs, and algorithms
- Model Theory Makes Formulas Large
- Notions of locality and their logical characterizations over finite models
- On the locality of arb-invariant first-order formulas with modulo counting quantifiers
- Periodic sets of integers
- Preservation and decomposition theorems for bounded degree structures
- The first order properties of products of algebraic systems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Tree acceptors and some of their applications
Cited in
(8)- A normal form theorem for first order formulas and its application to Gaifman's splitting theorem
- General normal forms for any additive logic
- Hanf normal form for first-order logic with unary counting quantifiers
- First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
- Learning concepts described by weight aggregation logic
- Model checking disjoint-paths logic on topological-minor-free graph classes
- Compound logics for modification problems
- Advances in algorithmic meta theorems (invited paper)
This page was built for publication: Gaifman normal forms for counting extensions of first-order logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5002820)
