RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2013, том 20, номер 2, страницы 139–156 (Mi mais304)  

Об эффективном моделировании неограниченного ресурса при помощи односчетчиковых контуров

В. А. Башкин

Ярославский государственный университет им. П. Г. Демидова, 150000 Россия, г. Ярославль, ул. Советская, 14

Аннотация: Вводится и исследуется специфический формализм счетчиковых автоматов с одним неограниченным счетчиком без проверки на ноль, обладающий достаточно простым почти периодическим поведением и удобным графическим представлением.
Положительным односчетчиковым контуром называется сильно связная односчетчиковая сеть (недетерминированный конечный автомат с одним счетчиком без проверки на ноль), содержащая по крайней мере один цикл, увеличивающий значение счетчика. Показано, что в положительном контуре бесконечная часть множества достижимости описывается арифметической прогрессией; получены оценки параметров этой прогрессии через структурные свойства диаграммы переходов. Представлен компактный и наглядный способ графического представления контура.
В общем случае односчетчиковые сети обладают такой же выразительной мощностью, как сети Петри с одной неограниченной позицией и магазинные автоматы с односимвольным стековым алфавитом. Показано, что произвольная односчетчиковая сеть может быть представлена в виде конечного дерева односчетчиковых контуров.
Вводится понятие правильно сформированной односчетчиковой сети. Односчетчиковая сеть называется правильно сформированной, если счетчик используется только при порождении бесконечных периодических подмножеств множества достижимых состояний. Показано, что для любой односчетчиковой сети существует эквивалентная (в смысле совпадения множеств достижимости) правильно сформированная сеть, которая может быть эффективно построена из соответствующего дерева контуров.

Ключевые слова: односчетчиковые сети, VASS, сети Петри, достижимость, контур.

Полный текст: PDF файл (519 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 519.71+004.021
Поступила в редакцию: 20.03.2013

Образец цитирования: В. А. Башкин, “Об эффективном моделировании неограниченного ресурса при помощи односчетчиковых контуров”, Модел. и анализ информ. систем, 20:2 (2013), 139–156

Цитирование в формате AMSBIB
\RBibitem{Bas13}
\by В.~А.~Башкин
\paper Об эффективном моделировании неограниченного ресурса при помощи односчетчиковых контуров
\jour Модел. и анализ информ. систем
\yr 2013
\vol 20
\issue 2
\pages 139--156
\mathnet{http://mi.mathnet.ru/mais304}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais304
  • http://mi.mathnet.ru/rus/mais/v20/i2/p139

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Моделирование и анализ информационных систем
    Просмотров:
    Эта страница:105
    Полный текст:34
    Литература:32

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019