Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width

DOI10.1007/3-540-48224-5_58MaRDI QIDQ4535802zbMATH OpenFDO

Authors Georg Gottlob, Reinhard Pichler

Publication date 16 June 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48224-5_58

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Hypergraphs (05C65) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
• Hypergraph acyclicity and propositional model counting
• scientific article; zbMATH DE number 5762365
• The dynamic complexity of acyclic hypergraph homomorphisms
• A formal context for closures of acyclic hypergraphs
• A model-theoretic characterisation of clique width
• Model checking lower bounds for simple graphs
• Model checking lower bounds for simple graphs
• Hypertree-width and related hypergraph invariants

Cited in

(5)

• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Tractability beyond -acyclicity for conjunctive queries with negation and SAT
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Some characterizations of \(\gamma \) and \(\beta \)-acyclicity of hypergraphs
• Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width

This page was built for publication: Hypergraphs in model checking: Acyclicity and hypertree-width versus clique-width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4535802)