Some results on regular expressions for multitape finite automata

Рассматриваются множества кортежей слов, принимаемых многоленточными конечными автоматами. Используется известная запись для регулярных выражений, которая описывает языки, принимаемые одноленточными автоматами. Однако интерпретация операции “конкатенация” в этом случае отличается. Алгебра событий для многоленточных конечных автоматов определяется аналогично определениям в алгебре событий, принимаемых одноленточными автоматами. Показано, что введенная алгебра является алгеброй Клини. Также показано, что некоторые известные результаты алгебры событий, принимаемых конечными одноленточными автоматами, правдивы и для этой алгебры.