Faster Existential FO Model Checking on Posets

DOI10.1007/978-3-319-13075-0_35zbMath1433.68216arXiv1409.4433OpenAlexW3187001576MaRDI QIDQ5892117

Sebastian Ordyniak, Jakub Gajarský, Petr Hliněný, Jan Obdržálek

Publication date: 11 September 2015

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

Full work available at URL: https://arxiv.org/abs/1409.4433

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

FO model checking on geometric graphs ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Faster Existential FO Model Checking on Posets ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Solving MAX-\(r\)-SAT above a tight lower bound
• Advice classes of parametrized tractability
• On problems without polynomial kernels
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• Parametrized complexity theory.
• Kernelization: New Upper and Lower Bound Techniques
• Closure properties of constraints
• Model checking existential logic on partially ordered sets
• Deciding First-Order Properties of Nowhere Dense Graphs
• Faster Existential FO Model Checking on Posets

This page was built for publication: Faster Existential FO Model Checking on Posets