Model checking existential logic on partially ordered sets

DOI10.1145/2603088.2603110zbMath1401.68187arXiv1405.2891OpenAlexW2064113986MaRDI QIDQ4635604

Simone Bova, Robert Ganian, Stefan Szeider

Publication date: 23 April 2018

Published in: ACM Transactions on Computational Logic, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

widthmodel checkingpartially ordered setsparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Partial orders, general (06A06) Logic in computer science (03B70) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items (8)

FO model checking on geometric graphs ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ A linear-time parameterized algorithm for computing the width of a DAG ⋮ Quantified Constraints in Twenty Seventeen ⋮ Reducing CMSO model checking to highly connected graphs ⋮ Faster Existential FO Model Checking on Posets ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the dimensions of ordered sets of bounded degree
• Recognition algorithms for orders of small width and graphs of small Dilworth number
• The isomorphism problem for varieties generated by a two-element algebra
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Color-coding
• Closure properties of constraints
• Deciding First-Order Properties of Nowhere Dense Graphs

This page was built for publication: Model checking existential logic on partially ordered sets