×

Completeness for first-order properties on sparse structures with algorithmic applications. (English) Zbl 1454.68054


MSC:

68Q25 Analysis of algorithms and problem complexity
03B70 Logic in computer science
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q60 Specification and verification (program logics, model checking, etc.)
68W01 General topics in the theory of algorithms
PDFBibTeX XMLCite
Full Text: DOI