О множестве достижимости автоматных трехсчетчиковых машин

Полный текст:


Аннотация

Доказывается, что существуют абстрактные счетчиковые машины, принадлежащие классу автоматных трехсчетчиковых машин, множество достижимости которых не является полулинейным.

Об авторах

Е. В. Кузьмин
Ярославский государственный университет им. П.Г. Демидова
Россия


Д. Ю. Чалый
Ярославский государственный университет им. П.Г. Демидова
Россия


Список литературы

1. Finkel A., Sutre G. An Algorithm Constructing the Semilinear Post* for 2-Dim Reset/Transfer VASS // In MFCS 2000, LNCS 1893, Springer, 2000. P. 353-362.

2. Finkel A., Sutre G. Decidability of Reachability Problems for Classes of Two-Counter Automata // In STACS 2000, LNCS 1770, Springer, 2000. P. 346-357.

3. Hopcroft J. E., Panswt J. On the Reachability Problem for 5-Dimensional Vector Addition Systems. Computer science technical report. Cornell University, 1976. -http://hdl.handle.net/1813/6102

4. Kouzmm E. V., Sokolov V.A. Communicating Colouring Automata // Proc. Int. Workshop on Program Understanding (sat. of PSI'03), 2003. P. 40-46.

5. Гинзбург С. Математическая теория контекстно-свободных языков. М.: Мир, 1970. 328 с.

6. Кузьмин Е. В., Соколов В. А. Взаимодействующие раскрашивающие процессы // Моделирование и анализ информационных систем. 2004. Т. 11, №2. С. 8 -17.

7. Кузьмин Е. В., Чалый Д. Ю. Об одном классе счетчиковых машин // Моделирование и анализ информационных систем. 2009. Т. 16, №2. С. 75 - 82.

8. Минский М. Вычисления и автоматы. М.: Мир, 1971. 268 c.

9. Mayr R. Lossy counter machines. Tech. Report TUM-I9827, Institut fu?r Informatik, TUM, Germany, October 1998.


Дополнительные файлы

Для цитирования: Кузьмин Е.В., Чалый Д.Ю. О множестве достижимости автоматных трехсчетчиковых машин. Моделирование и анализ информационных систем. 2009;16(3):77-84.

For citation: Kuzmin E.V., Chalyy D.J. On a reachability set of automaton 3-counter machines. Modeling and Analysis of Information Systems. 2009;16(3):77-84. (In Russ.)

Просмотров: 23

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)