Рассматривается задача спецификации структуры взаимодействий между объектами. Множество объектов и связей между ними представляется в виде размеченного ориентированного графа, а задача спецификации состоит в описании всех "хороших" графов: графов, которые задают допустимые структуры взаимодействия. По аналогии с классическим понятием регулярного выражения, определено понятие регулярного выражения над графами. При этом, если "кирпичиками" в обычных регулярных выражениях является строка символов, то в регулярных выражениях над графами роль "кирпичиков" выполняют графы