Для широкого класса задач, решаемых пользователями сетей ЭВМ, характерно применение форматных (структурированных) данных, представляющих собой набор взаимосвязанных полей. При этом каждое поле определяется своими атрибутами (яркостью, защищенностью, цветностью и т. д.) и расположением на устройстве отображения терминалов.

Фактически при диалоге пользователя с прикладной программой, работающей в центральной машине, необходимо передавать лишь те поля, значения которых изменяются пользователем или программой. Это позволяет резко сократить объем обмена (загрузку линии связи) и загрузку центральной ЭВМ. Такой режим может быть реализован при использовании «интеллектуальных» терминалов, т. е. терминалов, включающих микропроцессоры (или построенных на базе персональных ЭВМ). При этом в памяти терминала необходимо хранить библиотеки структур данных (форматов). Для организации библиотек необходимо разработать способы описания структур данных.

В работе рассматриваются структуры, используемые прикладными программами и терминалами, взаимодействующими при помощи протокола виртуального терминала. Специфика этих структур заключается в том, что они являются иерархическими, причем число уровней иерархии ограничено.

Для описания многоуровневых иерархических структур представляется целесообразным применение модели, базирующейся на теории ориентированных графов.

Данные, описываемые указанной моделью, задаются при помощи ориентированного дерева.

Иерархия, изображаемая в виде дерева, соответствует возможности использования подструктур, т. е. структур, являющихся частями всей структуры.

Число уровней в приведенной обзоре иерархии соответствует числу подструктур, вложенных в «объемлющие» их подструктуры. Промежуточные узлы дерева изображают подструктуры; листья дерева соответствуют полям данных.

Дерево, приведенное в обзоре, можно описать алгебраической моделью. Она строится на основе сопоставления множества дуг дерева подмножеству конечных последовательностей натуральных чисел.

Для решения этой задачи необходимо знание пути доступа к каждому узлу графа, представляющего структуру данных. Указанный путь задается с помощью графа, образуемого приводимым ниже преобразованием исходного графа. В дальнейшем такой преобразованный граф будем называть графом обходов.

Примером графа обходов является граф, изображенный в обзоре. На смотреть обзор под номером 3, а граф А задает структуру, состоящую из четырех полей данных. Граф обходов А показывает, каким образом вычисляются координаты полей данных на устройстве отображения терминала. Граф обходов дает возможность вычислять координаты каждого следующего по порядку (в принятой упорядоченности элементов А) узла исходного дерева.