Адрес e-mail:

Демонстрация программного обеспечения TRAG для проверки свойств графов

Демонстрация программного обеспечения TRAG для проверки свойств графов

9 июня в 18:15 в 107 БК состоится демонстрация программного обеспечения для проверки свойств графов «TRAG. Monadic second-order model checking with fly-automata».

Докладчик: Бруно Курсель (Bruno Courcelle), французский математик, известный своими исследованиями в теории графов, работает в лаборатории информатики (LABRI) Университета Бордо I во Франции.

Abstract:

An algorithmic meta-theorem states that every graph property expressible by a monadic second-order (MSO) sentence can be checked in linear time for graphs of bounded tree-width, or even, of bounded clique-width, given by appropriate algebraic terms. The standard proofs construct from MSO sentences and bounds on tree-width or clique-width  finite but huge automata intended to run on input terms encoding the input graphs.

By using fly-automata that do not store states and transitions but compute them whenever needed, we could implement  this result. And check in particular colorability and other NP-complete properties. In order to verify a graph property, we must input a clique-width term (corresponding to a decomposition of the graph witnessing an upper bound to its clique-width), together with a relevant fly-automaton. The property is verified if and only if the term is recognized by the automaton. This technique has been implemented in the system TRAG written in Common LISP by I. Durand.

The demonstration will show how to input a graph, to decompose it in several ways, to check coloring properties and Hamiltonicity. The system can build an automaton from a given MSO sentence.

Программное обеспечение TRAG можно найти на сайте. Документация доступна по ссылке.

На демонстрацию приглашаются студенты и специалисты, интересующиеся математикой и программированием. Вход свободный.

Мероприятие проходит в рамках конференции «Russian workshop on complexity and model theory», проходящей в МФТИ с 9 по 11 июня.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях