Вложение частичного порядка в линейный

9.7.6.02.5.6. Вложение
частичного порядка в линейный

Начало см. здесь и здесь.

Ахо А., Ульман Дж.
Теория синтаксического анализа, перевода и компиляции. Том 1.

Пер. с англ. М.: Мир 1978, cc. 59 — 60.

Определение частичных порядков см. здесь.

Определение линейных порядков см. здесь.

Определение ациклических графов см. здесь.

Определение вложенности (включения) отношений (в частности, отношений порядка) см. у Ю. А. Шрейдера здесь.

Рассуждение, изложенное в разделе "Метод" данного алгоритма, основано на Теореме 4.2. у Ю. А. Шрейдера; см. ее здесь.

Определение операций над отношениями (в частности, над отношениями порядка) см. у Ю. А. Шрейдера здесь.

Вопросы индукции по ациклическим графам разбираются здесь.