Twin-width I - Tractable FO Model Checking
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 24-minute IEEE conference talk on twin-width and its applications in tractable first-order model checking. Delve into concepts such as trigraphs, contraction sequences, unit intervals, and ktman graphs. Learn about Hamiltonian paths, bounded twin-width graph formula checking, and interpretations. Discover the role of magnetic stability in FO model checking and understand the dynamic programming approach used in this context. Gain insights from authors Idouard Bonnet, Eun Jung Kim, Stiphan Thomassi, and Rimi Watrigant from LIP, ENS Lyon, and LAMSADE, Paris-Dauphine University.
Syllabus
Introduction
Trigraphs
contraction sequence
something more
unit interval
ktman graphs
Hamiltonian path
Bounded Twin
Graph Formula Checking
Interpretations
Magnetic stability
FO model checking
Dynamic programming
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Human Computer InteractionIndependent Introduction à la logique informatique - Partie 2 : calcul des prédicats
Université Paris-Saclay via France Université Numerique System Validation (4): Modelling Software, Protocols, and other behaviour
EIT Digital via Coursera Formal Software Verification
University System of Maryland via edX Principles of Secure Coding
University of California, Davis via Coursera