Теория обобщенных линейных автоматов

• Published in: Кибернетика и системный анализ
• Date: 2009
• Main Author: Рысцов, И.К.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2009
• Subjects: Кибернетика
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/44301
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос.

Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведено також аналог теореми Мура про еквівалентні стани, а також лінійні аналоги теорем про установочні та діагностичні слова. Розглянуто застосування лінійних автоматів у математичній економіці. Linear and affine automata are considered in their general form. The concept of the dimension of a finite automaton is introduced and finite automata of maximal dimensions are shown to be possible. The state reachability problem in monomial form is proved to be undecidable for two-dimensional affine automata. An analogue of Moore’s theorem and theorems on homogenous and diagnostic words are also proved. An application of linear automata to mathematical economics is considered.