Задача продолжения с наименьшим возможным рангом частичной матрицы и ее приложение к теории линейных автоматов

В частичных матрицах над телом неизвестные элементы заменяются на знак $*$ . Для так возникших матриц $A$, $B$ определяются $AB$, $A+B$. Показывается, что при этом, напр., $A(BC)\subseteq(AB)C$, если $A$ всюду определена, где отношение $\subseteq$ частичного упорядочения означает покомпонентно: $\alpha\subseteq\beta$ тогда и только тогда, когда $\alpha=\beta$ или $\alpha=*\,$. Задача продолжения с наименьшим возможным рангом частичной матрицы $A$ в каком-либо классе $K$ заключается в нахождении всюду определенной матрицы $B\supseteq A$ из $K$, имеющей наименьший ранг, возможный при доопределении в классе $K$. Дается решение этой задачи для класса $K_0$ матриц, у которых строки линейно упорядочены отношением $\subseteq$. В качестве приложения указывается способ построения линейных автоматов наименьшей размерности, словарная функция которых продолжает частичную словарную функцию, определенную на всех словах длины не больше заданного значения $l$. Приводится оценка тех $l$, которые, обеспечивают единственность восстановления автомата или его размерности. Библ. 4.