?
О синхронной композиции детерминированных автоматов
Многие сложные системы представляются как композиция более простых в некотором смысле систем. Синхронная композиция соответствует одновременной работе всех каналов композиции и обычно используется при описании работы многомодульных аппаратных систем. Поведение аппаратных компонентов обычно описывается полностью определенными детерминированными автоматами, и вообще говоря, проектировщик ожидает, что и поведение всей композиции также описывается таким автоматом [1-3]. Несмотря на большое количество работ в этой области, в настоящий момент неизвестны необходимые и достаточные условия, при которых это возможно. В работе [1] авторы рассматривают синхронную композицию только автоматов Мура, т. е. автоматов, в которых выходной символ зависит только от текущего состояния автомата, т. е. не зависит от текущего входного символа. В монографии [2] авторы показывают, что, вообще говоря, достаточно иметь один автомат Мура в каждом цикле автоматной композиции. В работе [3] авторы уточняют это условие, требуя, чтобы в каждом цикле композиции из двух компонентов, по крайней мере, один внутренний выходной символ не зависел от внутреннего входного символа. Еще одно интересное условие, основанное на прогрессивном решении соответствующего автоматного уравнения, доказывается в [2].