Compact Labelings For Efficient First-Order Model-Checking

Details Compact Labelings For Efficient First-Order Model-Checking Compact Labelings For Efficient First-Order Model-Checking

2008-11-28

arxiv.org/abs/0811.4713v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider graph properties that can be checked from labels, i.e., bit sequences, of logarithmic length attached to vertices. We prove that there exists such a labeling for checking a first-order formula with free set variables in the graphs of every class that is \emph{nicely locally cwd-decomposable}. This notion generalizes that of a \emph{nicely locally tree-decomposable} class. The graphs of such classes can be covered by graphs of bounded \emph{clique-width} with limited overlaps. We also consider such labelings for \emph{bounded} first-order formulas on graph classes of \emph{bounded expansion}. Some of these results are extended to counting queries.

Affiliated with

Also associated with

No associations

Rating

Compact Labelings For Efficient First-Order Model-Checking does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compact Labelings For Efficient First-Order Model-Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compact Labelings For Efficient First-Order Model-Checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-710344