What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
Laurent Feuilloley, Nicolas Bousquet, Théo Pierron
Abstract
Local certification consists in assigning labels (called certificates) to the nodes of a network to certify a property of the network or the correctness of a data structure distributed on the network. The verification of this certification must be local: a node typically sees only its neighbors in the network. The main measure of performance of a certification is the size of its certificates.
Topics & Concepts
CertificationCorrectnessComputer scienceNode (physics)Property (philosophy)Measure (data warehouse)Tree (set theory)Computer networkLocal area networkMathematicsAlgorithmData miningEngineeringMathematical analysisStructural engineeringPolitical sciencePhilosophyLawEpistemologyAdvanced Graph Theory ResearchFormal Methods in VerificationComplexity and Algorithms in Graphs