Представление универсальных гиперграфических автоматов автономными выходными сигналами


https://doi.org/10.18255/1818-1015-2018-5-561-571

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


Аннотация

Гиперграфическими автоматами называются автоматы, у которых множества состояний и выходных символов наделены структурами гиперграфов, сохраняющимися функциями переходов и выходными функциями. Универсальные притягивающие объекты в категории таких автоматов представляются автоматами Atm(H1,H2) с гиперграфом состояний H1, гиперграфом выходных символов H2 и полугруппой входных символов S = EndH1 × Hom(H1,H2), которые называются универсальными гиперграфическими автоматами. Для такого автомата Atm(H1,H2) полугруппа входных символов S является производной алгеброй отображений, свойства которой взаимосвязаны со свойствами алгебраической структуры данного автомата. Это позволяет изучать универсальные гиперграфические автоматы с помощью исследования их полугрупп входных символов. В настоящей работе рассматривается проблема представления универсальных гиперграфических автоматов в их полугруппах входных сигналов: описывается представление универсального гиперграфического автомата в виде многосортной алгебраической системы, канонически построенной из автономных входных сигналов этого автомата. Эта конструкция является одним из инструментов доказательства относительно элементарной определимости рассматриваемых автоматов в классе полугрупп, которая позволяет проанализировать взаимосвязь элементарных свойств этих автоматов и их полугрупп входных сигналов. Основной результат работы дает решение этой задачи для универсальных гиперграфических автоматов над эффективными гиперграфами p-определимыми ребрами. Это достаточно широкий и весьма важный класс автоматов, так как он содержит, в частности, автоматы, у которых гиперграфы состояний и выходных символов являются плоскостями (например, проективными или аффинными) или разбиениями на классы нетривиальных эквивалентностей. Статья публикуется в авторской редакции.

Об авторах

Екатерина Владимировна Хворостухина
Саратовский государственный технический университет им. Гагарина Ю.А.
Россия

канд. физ.-мат. наук, доцент.

ул. Политехническая, 77, г. Саратов, 410054.



Владимир Александрович Молчанов
Саратовский национальный исследовательский государственный университет им. Н.Г. Чернышевского
Россия

докт. физ.-мат. наук, профессор.

ул. Астраханская, 83, г. Саратов, 410012.



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

1. Plotkin B.I., Geenglaz L.Ja., Gvaramija A. A., Algebraic structures in automata and databases theory, World Scientific, Singapore, 1992.

2. Simovici D., “On the theory of reduction of semilatticial automata”, Scientific Annals of the Alexandru loan Cuza University of Iasi (New Series), 22:1 (1976), 107-110.

3. Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. I”, Acta Sci. Math., 24:3-4 (1963), 244-250 (in Russian).

4. Gecseg F., “O proizvedeniyakh uporyadochennykh avtomatov. II”, Acta Sci. Math., 25:1-2 (1964), 124-128 (in Russian).

5. Eilenberg S., Automata, languages and machines. Volume B, Academic Press, New York, San Francisco, London, 1976.

6. Bretto A., Hypergraph theory. An Introduction, Springer, Cham, 2013.

7. Hartshorne R., Foundations of Projective Geometry, Ishi Press, New York, 2009.

8. Molchanov V. A., Khvorostukhina E. V., “Ob abstraktnoy opredelyaemosti universalnykh gipergraficheskikh avtomatov polugruppami ikh vkhodnykh signalov”, Issledovaniya po algebre, teorii chisel, funktsionalnomu analizu i smezhnym voprosam, 2016, № 8, 67-69 (in Russian).

9. Molchanov V. A., Khvorostukhina E. V., “On problem of concrete characterization of universal automata”, Loba,chevskii Journal of Mathematics, 38:4 (2017), 664-669.

10. Ershov Yu. L., Problemy razreshimosti i konstruktivnye modeli, Nauka, Moscow, 1980 (in Russian).

11. Molchanov A. V., “Endomorphism semigroups of weak p-hypergraphs”, Russian Mathematics (Izvestiya VUZ. Matematika,), 44:3 (2000), 77-80.


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

Для цитирования: Хворостухина Е.В., Молчанов В.А. Представление универсальных гиперграфических автоматов автономными выходными сигналами. Моделирование и анализ информационных систем. 2018;25(5):561-571. https://doi.org/10.18255/1818-1015-2018-5-561-571

For citation: Khvorostukhina E., Molchanov V. Universal Hypergraphic Automata Representation by Autonomous Input Symbols. Modeling and Analysis of Information Systems. 2018;25(5):561-571. https://doi.org/10.18255/1818-1015-2018-5-561-571

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

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

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


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


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