Efficient First-Order Model-Checking Using Short Labels

DOI10.1007/978-3-540-69311-6_18MaRDI QIDQ3507329zbMATH OpenOpenAlexFDO

Authors Cyril Gavoille, Mamadou Moustapha Kanté, Bruno Courcelle

Publication date 19 June 2008

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69311-6_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Compact labelings for efficient first-order model-checking
• First-order and monadic second-order model-checking on ordered structures
• Generalized model-checking over locally tree-decomposable classes
• scientific article; zbMATH DE number 2086422
• Logical labeling schemes

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 969067 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Compact Forbidden-Set Routing
• Compact and localized distributed data structures
• Connectivity check in 3-connected planar graphs with obstacles
• Deciding first-order properties of locally tree-decomposable structures
• Finding Branch-Decompositions and Rank-Decompositions
• First-order queries on structures of bounded degree are computable with constant delay
• Generalized model-checking over locally tree-decomposable classes
• Graph minors. V. Excluding a planar graph
• Linear time low tree-width partitions and algorithmic consequences
• Logic, graphs, and algorithms
• Query efficient implementation of graphs of bounded clique-width
• Upper bounds to the clique width of graphs

Cited in

(2)

• Compact labelings for efficient first-order model-checking
• Generalized model-checking over locally tree-decomposable classes

This page was built for publication: Efficient First-Order Model-Checking Using Short Labels

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