Теория обобщенных линейных автоматов
Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведе...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2009 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/44301 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862735912045117440 |
|---|---|
| author | Рысцов, И.К. |
| author_facet | Рысцов, И.К. |
| citation_txt | Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведено також аналог теореми Мура про еквівалентні стани, а також лінійні аналоги теорем про установочні та діагностичні слова. Розглянуто застосування лінійних автоматів у математичній економіці.
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.
|
| first_indexed | 2025-12-07T19:51:06Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-44301 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T19:51:06Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Рысцов, И.К. 2013-05-28T19:00:23Z 2013-05-28T19:00:23Z 2009 Теория обобщенных линейных автоматов / И.К. Рысцов // Кибернетика и системный анализ. — 2009. — № 1. — С. 10-21. — Бібліогр.: 18 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44301 519.713.4 Визначено лінійні та афінні автомати у загальному вигляді. Введено поняття розмірності для скінчених автоматів і доведено, що існують автомати максимальної розмірності. Доведено, що проблема досяжності станів у мономіальній формі не є алгоритмічно-розв’язною для двовимірних афінних автоматів. Доведено також аналог теореми Мура про еквівалентні стани, а також лінійні аналоги теорем про установочні та діагностичні слова. Розглянуто застосування лінійних автоматів у математичній економіці. 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. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Теория обобщенных линейных автоматов Теорія узагальнених лінійних автоматів Theory of general linear automata Article published earlier |
| spellingShingle | Теория обобщенных линейных автоматов Рысцов, И.К. Кибернетика |
| title | Теория обобщенных линейных автоматов |
| title_alt | Теорія узагальнених лінійних автоматів Theory of general linear automata |
| title_full | Теория обобщенных линейных автоматов |
| title_fullStr | Теория обобщенных линейных автоматов |
| title_full_unstemmed | Теория обобщенных линейных автоматов |
| title_short | Теория обобщенных линейных автоматов |
| title_sort | теория обобщенных линейных автоматов |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44301 |
| work_keys_str_mv | AT ryscovik teoriâobobŝennyhlineinyhavtomatov AT ryscovik teoríâuzagalʹnenihlíníinihavtomatív AT ryscovik theoryofgenerallinearautomata |